<s>[INST] Show that $T(n)= 2^{n+1} - 1$ Show that $T(n)= 2^{n+1} - 1$, for the following,
$$
  T(n) = \cases{        1       & if, $n=0$ \cr
                 T(n-1) + 2^n & otherwise}
$$
I did it as follows,
\begin{align*}
   T(n) = T(n-2) + 2^{n-1} + 2^n  \\
   T(n) = T(n-3) + 2^{n-2} + 2^{n-1} + 2^n\\
   &\vdots\\
   T(n) = T(n-(n-1)) + 2^{n-n}+ \dots+ 2^{n-1} + 2^n
\end{align*}
From the last call, I can see that,
\begin{align*}
   T(0) = T(1) + 2^{0}+ \dots+ 2^{n-1} + 2^n  \\
   1 = T(1) + 2^{0}+ \dots+ 2^{n-1} + 2^n\\
   1 = T(1) + \sum_{i=1}^{n}2^i\\
   1 = T(1) + \frac{2^{n+1}-1}{2-1}\\
\end{align*}
How we can get rid of 1 and T(1) as they appeared in my solution please?
 [/INST] Your work contains a number of errors.
First of all, your equation $$T(n-1) = T(n-2) + 2^{n-1} + 2^n$$ makes no sense, since $$T(n) = T(n-1) + 2^n \tag{1}$$ from the given definition implies $$T(n-1) = T(n-2) + 2^{n-1}, \tag{2} $$ simply by replacing $n$ with $n-1$.
What you probably intended to write is
$$T(n) = T(n-1) + 2^n = \left(T(n-2) + 2^{n-1}\right) + 2^n,$$  where we "unfolded" the recursion by substituting Equation $(2)$ into Equation $(1)$.  If you do it again, we get
$$T(n) = T(n-3) + 2^{n-2} + 2^{n-1} + 2^n.$$
This is what you want to write.  The left hand side does not change.
Then a complete unfolding of the recursion gives
$$T(n) = T(0) + 2^1 + 2^2 + \cdots + 2^n,$$ and since $T(0) = 1$, we get $$T(n) = \sum_{k=0}^n 2^k = \frac{2^{n+1} - 1}{2-1} = 2^{n+1} - 1,$$ as claimed.
</s>