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.
$$\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}$$