Friday, September 4, 2015

algebra precalculus - Spivak Chapter 2 Question 1 (i)


I don't understand Spivak's proof by induction of this exercise:


Prove by induction


$$1^2 + \ldots + n^2 = {n(n+1)(2n+1))\over 6}$$


It's true for $n = 1$ Then the proof continues adding $(k+1)^2$ like:


$$1^2 + \ldots + n^2 = {(n(n+1)(2n+1)\over 6} + (k+1)^2$$


After performing the calculations, this results as: ${(k+1)(k+2)(2(k+1)+1)\over 6}$ which is a proof that the equation is right. If that's the case, I should replace $n = 2$ and get 4 because $2^2 = 4$ but instead I'm getting 5.


Actually it's true for $n = 1$ but for me it seems that it's not true for n+1. I'm sure I'm doing something wrong but where.



Answer



The proposition we want to prove is $$P(n):\quad 1^2 + 2^2 + \cdot + n^2 = \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$$


For $n = 2$:


$$P(2):\quad 1^2 + 2^2 = 5 = \frac{2 (2+1)(2\cdot 2+1)}{6}$$


Similarly, $P(3) = 1^2 + 2^2 + 3^2 = 14 = \frac{3(4)(7)}{6}$.


It holds for $n = k+1$ having assumed it holds for $n = k$ (this assumption we call the inductive hypothesis.) That's crucial to understanding proof by induction. $$[P(1) \land (P(k)\rightarrow P(k+1))]\implies P(n)\text{ for } n \geq 1$$ where $P(n)$ is the proposition we are attempting to prove.


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