Thursday, May 26, 2016

discrete mathematics - How do I find a flaw in this false proof that $7n = 0$ for all natural numbers?

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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...