Wednesday, 13 March 2013

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 nN, 7n=0.



Let P(n) denote the statement that 7n=0.



Base case: Show P(0) holds.




Since 70=0, P(0) holds.



Inductive step: Assume 7·j=0 for all natural numbers j where 0jk (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 nN.




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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...