Flawed strong induction of $2^a = 2$.

Question

I'm trying to prove that for all positive integers $a$, that $2^a = 2$.

Obviously, I know this is false, but I was given an induction proof and I need to find the error.

The base case is that for $a = 1$, it's true that $2^1 = 2$.

For the induction step, we let $x$ be an arbitrary positive integer. The induction hypothesis is that $2^y = 2$ for all integers $y$ such that $1 \leq y \leq x$, with the same restriction on $x$ as mentioned. We need to prove that $2^{x + 1} = 2$.

$2^{x+1} = \frac{2^x \cdot 2^x}{2^{x - 1}}$

$= \frac{2 \cdot 2}{2}$ by the induction hypothesis

$= 2$

This completes strong induction, so $2^a = 2$ for all positive integers $a$.

Answer 1

The issue is that in going from $x$ to $x+1$ you assume the hypothesis is true for both $x$ and $x-1$. But if $x=1$ then $x-1$ is out of range, so the step from $1$ to $2$ doesn't work.

Answer 2

You can pretty much always find the error in an induction proof by just stepping through it yourself. An induction proof allows you to deduce $\phi(a)$ from all smaller $\phi(i)$; you know the statement is false when $a=2$; so write out the proof setting $a=2$ throughout, and see what false statement you wrote down.