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.
Answer
Hint: Try the inductive step with $k = 0$.
No comments:
Post a Comment