Show that $\sum_{i=0}^{n-1} 2^i = 2^n - 1$ This is a problem from a book with no solution.
Show that: $$\sum_{i=0}^{n-1} 2^i = 2^n - 1$$
without using the formula for geometric series.
My lengthy solution is as follows:
Try with $n = 1, 2, 3$ and prove that it works. Which it does.
$$\sum_{i=0}^{n-1} 2^i = 2^n - 1$$ for $n = {1,2,3}$
Assume that it works for $n = p$.
$$\sum_{i=0}^{p-1} 2^i = 2^p - 1$$
Show that it works for $n = p + 1$
$$\begin{align*}
LHS_{p+1} =& \sum_{i=0}^p 2^i\\
=& \sum_{i=0}^{p-1} 2^i + 2^p\\
=& LHS_p + 2^p\\
=& RHS_p + 2^p\\
=& 2^p - 1 + 2^p\\
=& 2(2^p) - 1\\
=& 2^{p+1} - 1\\
=& RHS_{p+1} 
\end{align*}$$
And they match so they must be the same. Did I do this right? :)
 A: Your induction proof is fine, though you need only one initial case.
Here’s a short solution:
$$2\sum_{k=0}^{n-1}2^k=\sum_{k=0}^{n-1}2^{k+1}=\sum_{k=1}^n2^k=\sum_{k=0}^{n-1}2^k+2^n-1\;,$$
so $$\sum_{k=0}^{n-1}2^k=2^n-1\;.$$
(This is essentially proving the formula for the sum of a finite geometric series, but just in this special case.)
A: You are proving it by induction and have the correct approach.  You only have to try one base case.  Then instead of $LHS_{p+1}$ it would be better to use the sum, so
Assume $\sum_{i=0}^{p-1} 2^i = 2^p - 1$ then 
$\sum_{i=0}^{p} 2^i = 2^p+\sum_{i=0}^{p-1} 2^i = 2^p+2^p - 1=2^{p+1}-1$
and you are done
A: Your proof works just fine.  There's also a combinatorial proof expressing the same principle: $2^{i-1}$ is the number of non-zero $i$-digit binary numbers (since any such begins with '1' and has $i-1$ 'free' digits after), so $\sum_{i=1}^{n} 2^{i-1}$ (or equivalently $\sum_{j=0}^{n-1}2^j$) is the total number of (non-zero) binary numbers of $n$ or fewer binary digits - which there are clearly $2^n-1$ of (since they're all the numbers less than $2^n$).
A: Sure that works. With proofs by induction, you don't need to check so many initial cases. Just checking it for the $n = 1$ case is more than enough. 
A: Hint: You can avoid induction entirely if you observe that $$\sum_{i=0}^{n-1}2^i=(2-1)\sum_{i=0}^{n-1}2^i$$ and distribute.
