Wednesday, November 22, 2017

induction - Is this backwards reasoning?



Yesterday I was answering a question on induction:
Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear



Basically, I was proving a certain formula using induction.




$$\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$



The base case it's okay. Now let's assume the formula is valid for $N$, we want to demonstrate the following, that is



$$\sum\limits_{i=0}^{N+1} i^2 = \frac{(N+1)(N+2)(2(N+1)+1)}{6} \ \ (1) $$



that is to say



$$\sum\limits_{i=0}^{N} i^2 + (N + 1)^2 = \frac{(N+1)(N+2)(2(N+1)+1)}{6}\ \ (2) $$




$\Rightarrow$ (thanks to induction hypothesis)



$$\frac{N(N+1)(2N+1)}{6} + (N+1)^2 = \frac{(N+1)(N+2)(2(N+1)+1)}{6}\ \ (3) $$



Then I concluded that if one show that (3) is true (by simplifying, and getting $0 = 0$) then the proof is valid and complete.



Some argue this is backwards reasoning; but I can't understand why.



The equalities that I use to go from (1) to (2) to (3) can be used for going from (3) to (2) to (1)




My argument is, if (3) simplifies to $0=0$, so it is equivalent with that and therefore True, also (2) is True, and also (1) is true, which was what I wanted to prove.



Is this backwards reasoning, and if so someone please explain me why


Answer



EDIT: The question has been updated, so the answer is mostly irrelevant (but it still shows how one word here or there can change quite a lot :-) )






I don't think your reasoning was backwards, but its presentation and wording might have been understood so. Specifically, stating "we have" implies it's something we either assume or have already proven rather than something we're trying to prove. Presenting the same reasoning slightly differently could avoid the ambiguity:




Let's evaluate the sum for $N+1$:
$$\sum_{i=1}^{N+1} i^2 = \sum_{i=1}^{N} i^2 + (N+1)^2$$
The induction hypothesis tells us that $$\sum_{i=1}^{N} i^2 = \frac{1}{6}N(N+1)(2N+1)$$ so
$$\sum_{i=1}^{N} i^2 + (N+1)^2 = \frac{1}{6}N(N+1)(2N+1) + (N+1)^2$$
Simplifying the right-hand side yields
$$\frac{1}{6}N(N+1)(2N+1) + (N+1)^2 = \frac{1}{6}(N+1)\left((N+1)+1\right)\left(2(N+1)+1\right)$$



Finally, combining the equalities shows that the statement holds for $N+1$ as well, thus completing the inductive step.


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...