We can write down the first few terms of the sequence that gives the number of grains of rice you receive on day We get
since, for example, on day 4, you take the number of grains of rice you had on day 3 (all seven of them), double that and add 1, to get 15. The next day you would get
By actually computing these values, we see right away what the recurrence relation is:
This is justified because the problem the sequence is modeling says that we double the number of grains each day, and then add 1. We can read the recurrence relation right off the problem.
The original question asked about
We could find this using the recurrence relation, but we would first need to find
and to find that we would need
which requires
first, and so on. While Iβm sure we could work all the way back to
which we already found, this sounds like a lot of work.
It would be so much nicer to have a closed formula. If we could
solve the recurrence relation and find that closed formula, we could just substitute
for
Letβs guess. It looks like the sequence is close to which has closed formula That sequence has terms one greater than the terms in our sequence, so we might guess that
To be clear, we have no good reason to believe this guess is correct, but maybe later in this chapter we will. However, if it is correct, then we are golden (and incredibly sick of rice):