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.