# Finding closed form of recurrence relation

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.

• $\sum_{i=2}^n 2^i=\sum_{i=0}^{n-2} 2^{i+2}$ – user160738 Mar 18 '17 at 4:49
• @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. – BabaSvoloch Mar 18 '17 at 5:01
• 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}$ – 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}