I'm having a really hard time with this proof by induction:
Prove this formula by induction: $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$. Easy enough, right? Wrong. I have to do it using the following identities:
- $\binom{2}{2} + \binom{3}{2} + \binom{4}{2} + ... + \binom{n}{2} = \binom{n + 1}{3}$
- $m^2 = 2\binom{m}{2} + m \text{ for } m \geq 2$
I've attempted this many times. I'm officially stumped.
Thanks in advance.
Interestingly, it doesn't appear you need induction with those identities. Here's my take on it (if this isn't what you're looking for, you ought to be able to write an inductive proof with the same steps): $$\sum_{k=1}^n k^2 = 1+\sum_{k=2}^n k^2 = 1+\sum_{k=2}^n \left(2 {k\choose 2} +k\right) = 1+\left(\frac{n(n+1)}{2}-1\right)+2\sum_{k=2}^n {k\choose 2}.$$ The third equality follows from identity (2). I then pulled out the sum of the first $k$ integers using the well-known summation formula (the $-1$ is because we started at $k=2$). Ignoring the other terms for a moment, identity (1) gives us $$\sum_{k=2}^n {k\choose 2} = {n+1\choose 3} = \frac{(n+1)!}{3!(n-2)!} = \frac{(n+1)n(n-1)}{6},$$ where I've applied the definition of "choose" and canceled out the common factors of the factorials. Substituting this into what we had before and finding a common denominator, $$\sum_{k=1}^n k^2 = \frac{n(n+1)}{2}+2\cdot\frac{n(n+1)(n-1)}{6} = \frac{n(n+1)}{6}\left(3+2(n-1)\right) = \frac{n(n+1)(2n+1)}{6}.$$ I hope this helps!