I am trying to prove the recurrence $2T(n-1) + 1$ has the bound $\theta(2^{n})$. $T(1) = \theta (1)$
My attempted solution:
\begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 \\ &= 2 \{ 2 \{ 2T( n - 3 ) + 1 \} + 1 \} + 1 \\ & \ldots \\ &= 2^{i}T(n-i)+\sum_{i=0}^{k} 2^{i} + 1. \end{align*}
I then proceed to substitute $n-1$ for $i$ which gives me
\begin{align*} & 2^{n-1}T(n-(n-1)) + \sum_{i=0}^{n-1} 2^{i} + 1 \\ &= 2^{n-1}T(n-n+1) + \sum_{i=0}^{n-1} 2^{i} + \sum_{i=0}^{n-1} 1 \\ &= 2^{n-1}T(1) + 2^{n-1+1} + n - 1 \\ &= 2^{n-1}\theta(1) + 2^{n} + n - 1\\ \end{align*}
At this point I can see that $2^{n}$ is the dominating factor, however in the solution hints of my book it states that I should use $i = n$. However when I do that I get $T(0)$.
I suspect there is something wrong with my substitution/unraveling step, however I can't seem to figure it out. Any help would be appreciated