Question

Prove by mathematical induction: 1+2+2^2+2^3+....+2^n-1=2^n-1

Answer 1

First show the statement holds for the base case (presumably $n=1$):

$\displaystyle\sum_{i=1}^1 2^{i-1}=2^{1-1}=2^0=1$

Meanwhile, the right hand side evaluates to $2^1-1=2-1=1$, so the base case holds.

Now assume the formula holds for $n=k$; that is,

$\displaystyle\sum_{i=1}^k 2^{i-1}=2^0+2^1+\cdots+2^{k-1}=2^k-1$

and use this hypothesis to show that the formula holds for $n=k+1$. You have

$\displaystyle\sum_{i=1}^{k+1}2^{i-1}=2^k+\sum_{i=1}^k 2^{i-1}=2^k+2^k-1=2\times2^k-1=2^{k+1}-1$

so the formula holds and the proof is complete.