Solve the recurrence relation (using iteration?)

Question

$a_n = a_{n-1} + 1 + 2^{n-1}\\ a_0 = 0$

Not sure how to iterate with the exponent term.

Here's what I got:

$= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-1} = a_{n-2} + 2 + 2(2^{n-1})\\ = (a_{n-3} + 1 + 2^{n-1}) + 2 + 2(2^{n-1}) = a_{n-3} + 3 + 3(2^{n-1})\\ \vdots\\ = a_0 + n + n(2^{n-1}) $

That doesn't seem to work though it works for n=0,1 but not n=2 that should be 5 but my solution gives 6. So

$= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-2} = a_{n-2} + 2 + 2^{n-1} + 2^{n-2}\\ = (a_{n-3} + 1 + 2^{n-1}) + 2 + 2^{n-1}+2^{n-2} = a_{n-3} + 3 + 2^{n-1}+2^{n-2}+2^{n-3}\\ \vdots\\ = a_0 + n + ? $

Answer 1

We have:

$a_n\\= (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) +\cdots + (a_2 - a_1) + a_1\\= (1+2^{n-1}) +(1+2^{n-2}) +\cdots +(1+2^1) + 2\\= n+1 + 2(1+ 2 + \cdots + 2^{n-2})\\= n+1+2(2^{n-1}-1)\\= n-1+2^n$.

Answer 2

Iteration will work:

$$\begin{align*} a_n&=a_{n-1}+1+2^{n-1}\\ &=a_{n-2}+1+2^{n-2}+1+2^{n-1}\\ &=a_{n-2}+2+2^{n-2}+2^{n-1}\\ &=a_{n-3}+1+2^{n-3}+2+2^{n-2}+2^{n-1}\\ &=a_{n-3}+3+2^{n-3}+2^{n-2}+2^{n-1}\\ &\;\vdots\\ &=a_{n-k}+k+\sum_{i=1}^k2^{n-i}\\ &\;\vdots\\ &=a_{n-n}+n+\sum_{i=1}^n2^{n-i}\\ &=n+\sum_{i=0}^{n-1}2^i\\ &=n+2^n-1\\ &=2^n+n-1 \end{align*}$$