I am struggling with recurrence relations and would really appreciate some help.

I'm supposed to find a closed form for the following recurrence relation:

$a_{n} = a_{n-1} + 2^{n}$ for $n \geq 2$ with initial condition $a_{1} = 1$

I wrote out the expanded form for the next few values of a to make it easier to spot the relationship between them:

$a_{1} = 1$

$a_{2} = 1 + 2^{2}$

$a_{3} = 1 + 2^{2} + 2^{3}$

$a_{4} = 1 + 2^{2} + 2^{3} + 2^{4}$

... etc.

So what I concluded is that:

$a_{n} = (\sum_{i=2}^{n} 2^{i}) + 1$

... But I don't know how to express that in closed form. I know that:

$\sum_{i=0}^{n} r^{i} = \frac{r^{n+1}-1}{r-1}$

But the index for the sum that I came up with starts at 2, not at 0. I don't know how to account for that, and I don't know if what I've done so far is correct.

Any help would be very much appreciated. Thank you.

  • 1
    $\begingroup$ $\sum_{i=2}^n 2^i=\sum_{i=0}^{n-2} 2^{i+2}$ $\endgroup$ – user160738 Mar 18 '17 at 4:49
  • $\begingroup$ @user160738 thanks! I'm still not sure how to convert a sum that goes from 0 to n-2 into a sum that goes from 0 to n though, for my closed form of r^i. $\endgroup$ – BabaSvoloch Mar 18 '17 at 5:01
  • 1
    $\begingroup$ Just plug in $n-2$ into the formula you have to get $\sum_{i=0}^{n-2} r^i=\frac{r^{n-1}-1}{r-1}$ $\endgroup$ – user160738 Mar 18 '17 at 5:06

$$\begin{align} a_n\;\;\ -a_{n-1}&=2^n\\ a_{n-1}-a_{n-2}&=2^{n-1}\\ a_{n-2}-a_{n-3}&=2^{n-2}\\ &\vdots\\ a_2\;\;\ -a_1\;\;\ &=2^2\\ \text{Summing by telescoping gives}\qquad \qquad \\ a_n\;\;\ -\underbrace{a_1}_1\;\;\ &=\frac {2^2(2^{n-1}-1)}{2-1}\\ a^n&=\color{red}{2^{n+1}-3} \end{align}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.