Proof By Induction Help?

Question

I've been working through proof by induction and i'm stuck on this question. Can somebody provide some help? $$ 2^n-1=\sum_{i=0}^{n-1}2^i\text{ for }n\ge 1$$

Answer 1

Hint : $2^{n+1}-1=2(2^n-1)+1$.

Answer 2

Guest has given a very good hint. Alternatively, you can generalize:

For any $x,y \in \Bbb{R}$ then $$x^n-y^n = (x-y)\sum_{i=0}^{n-1}y^ix^{n-1-i}$$ If you prove this by induction, then your proof follows as a special case of $x=2, y=1$. Your original proof is probably easier than this one, but this one is a good result to have regardless.

Answer 3

Although the hint by Guest is quite good, as graydad pointed out, I imagine you are probably struggling with some summation manipulation (or am I wrong?). Here's a brief sketch (I imagine you can fill in all of the fine details and make the argument flow like a written proof should): \begin{align} 2^{k+1}-1 &= 2\cdot(2^k-1)+1\\[1em] &= 2\cdot\sum_{i=0}^{k-1}2^i + 1\\[1em] &= \sum_{i=1}^k2^i + 1\\[1em] &= \sum_{i=0}^k2^i. \end{align} Does that make more sense now?

Answer 4

First, show that this is true for $n=1$:

• $2^1-1=\sum\limits_{i=0}^{1-1}2^i$

Second, assume that this is true for $n$:

• $2^n-1=\sum\limits_{i=0}^{n-1}2^i$

Third, prove that this is true for $n+1$:

• $2^{n+1}-1=2\cdot2^n-1$

• $2\cdot2^n-1=2\cdot2^n-2+1$

• $2\cdot2^n-2+1=2\cdot(2^n-1)+1$

• $2\cdot(2^n-1)+1=1+2\cdot(2^n-1)$

• $1+2\cdot(2^n-1)=1+2\cdot\sum\limits_{i=0}^{n-1}2^i$ assumption used here

• $1+2\cdot\sum\limits_{i=0}^{n-1}2^i=1+\sum\limits_{i=1}^{n}2^i$

• $1+\sum\limits_{i=1}^{n}2^i=2^0+\sum\limits_{i=1}^{n}2^i$

• $2^0+\sum\limits_{i=1}^{n}2^i=\sum\limits_{i=0}^{n}2^i$