# What is wrong with this induction proof?

What is wrong with this "proof" by strong induction?

"Theorem": For every non-negative integer $n, 5n = 0$.
Basis Step: $5(0) = 0$
Inductive Step: Suppose that $5j = 0$ for all non-negative integers j with $0 \le j \le k$. Write $k + 1 = i + j$, where $i$ and $j$ are natural numbers less than $k + 1$. By the inductive hypothesis, $5(k + 1) = 5(i + j) = 5i + 5j = 0 + 0 = 0.$

My initial thought is that strong induction used variables less than $k$ and greater than $k$. $k-1$ is shown in forms of $i$ and $j$ but no $k+1$ is used.

## 2 Answers

Hint: Try the inductive step with $k = 0$.

• Sorry its not ringing any bells. Only thing I can think of with this hint is that 5(k)=0. – Extreme112 Nov 3 '14 at 5:05
• If $k = 0$, then $k+1 = 1$. Can you find $i,j < 1$ with $i+j = 1$? – André 3000 Nov 3 '14 at 5:57

Strong induction would require you to show two base cases for this proof ($n = 0$ and $n = 1$).

Think about it: It is only guaranteed from the base case that the statement holds for numbers $k$ so that $0 \leq k \leq 0$. The proof takes two numbers $i,j$ with $0 \leq i,j \leq 0$ to proceed with induction beyond this point. The problem lies in the fact that $i$ and $j$ then clearly must both be $0$. The proof wants induction to proceed beyond this point by having them add up to the next value (i.e. $1$). This clearly is not possible.

• "Strong induction would require you to show two base cases for this proof ($n=0$ and $n=1$)." seems a bit misleading. The reason why one base case is not enough here is that this particular inductive step given in the "proof" does not work with $k=0$, not some intrinsic property of strong induction. – JiK Nov 3 '14 at 9:43
• I said "for this proof". I didn't mean to make it sound too general. I was just trying to show why this specific proof required two. – user134593 Nov 3 '14 at 14:21