Proof by Induction for Natural Numbers

Question

Show that if the statement

$$1 + 2 + 2^{2} + ... + 2^{n - 1} = 2^{n}$$

is assumed to be true for some $n,$ then it can be proved to be true for $n + 1.$ Is the statement true for all $n$?

Intuitively, then I don't think it holds for all $n.$

Answer 1

If we assume that $1+2+\cdots+2^{n-1}=2^n$, we can easily prove that $1+2+\cdots+2^n=2^{n+1}$. For $$1+2+\cdots+2^n=(1+2+\cdots+2^{n-1})+2^n=2^n+2^n=2^{n+1}.$$

But of course it is not true that $1+2+\cdots+2^{n-1}=2^n$. The base case $n=1$ does not hold. For then $1+2+\cdots+2^{n-1}=1\ne 2^1$.

The whole point of this exercise is that in order to prove a result by induction, we must do the induction step (which worked) and we must verify the base case (which failed).

In fact, $1+2+\cdots+2^{n-1}=2^n-1$. The proof is straightforward.

Answer 2

So, let $n = 3 \in \mathbb{N}$. Then we have, $$2^0+2^1+2^2=1+2+4=7 \neq 2^3$$

Answer 3

This statement is false. According to this statement:

$1+2^{1}=2^{2} \\ 3=4$

which is false.

Answer 4

Let premise $P(n)$ be $\sum\limits_{k=0}^{n-1} 2^k = 2^n$

If we assume $P(n)$, for some $n{\geq}1$ , then $\sum\limits_{k=0}^n 2^k = 2^n+2^n = 2^{n+1}$, which means $P(n+1)$

So we can indeed show: $\forall n{\geq}1:P(n)\to P(n+1)$

This is not enough!   In order to prove $\forall n{\geq}1:P(n)$ we need to show $P(1)\;\wedge\; \forall n{\geq}1:P(n)\to P(n+1)$.

That is to say, the iterative step alone is not sufficient, a proof by induction also requires demonstrating some base case.

In this case, since $P(1)\equiv (2^0=2^1)$, we cannot prove it.

---

Indeed, rather we can prove:

$$\forall n{\geq}1: \sum_{k=0}^{n-1} 2^k= 2^n -1$$