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