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*2^k-1=2^(k+1)-1`

so the formula holds and the proof is complete.