This is my last homework problem and I've been looking at it for a while. I cannot nail down what is wrong with this proof even though its obvious it is wrong based on its conclusion. Here it is:
Find the flaw in the following bogus proof by strong induction that
for all $n \in \Bbb N$, $7n = 0$.
Let $P(n)$ denote the statement that $7n = 0$.
Base case: Show $P(0)$ holds.
Since $7 \cdot 0 = 0$, $P(0)$ holds.
Inductive step: Assume $7·j = 0$ for all natural numbers $j$ where $0 \le j \le k$ (induction hypothesis). Show $P(k + 1)$: $7(k + 1) = 0$.
Write $k + 1 = i + j$, where $i$ and $j$ are natural numbers less than $k + 1$. Then, using the induction hypothesis, we get $7(k + 1) = 7(i + j) = 7i + 7j = 0 + 0 = 0$. So $P(k + 1)$ holds.
Therefore by strong induction, $P(n)$ holds for all $n \in \Bbb N$.
So the base case is true and I would be surprised if that's where the issue is.
The inductive step is likely where the flaw is. I don't see anything wrong with the strong induction declaration and hypothesis though and the math adds up! I feel like its so obvious that I'm just jumping over it in my head.
No comments:
Post a Comment