sequences and series - Sum of First $n$ Squares Equals $frac{n(n+1)(2n+1)}{6}$

I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:

$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$

I really have no idea why this statement is true. Can someone please explain why this is true and if possible show how to arrive at one given the other?

Answer

You can easily prove it by induction.

One way to find the coefficients, assuming we already know that it's a degree $3$ polynomial, is to calculate the sum for $n=0,1,2,3$. This gives us four values of a degree $3$ polynomial, and so we can find it.

The better way to approach it, though, is through the identity
$$ \sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}. $$
This identity is true since in order to choose a $(k+1)$-subset of $n+1$, you first choose an element $t+1$, and then a $k$-subset of $t$.

We therefore know that
$$ \sum_{t=0}^n A + Bt + C\binom{t}{2} = A(n+1) + B\binom{n+1}{2} + C\binom{n+1}{3}. $$
Now choosing $A=0,B=1,C=2$, we have
$$ A+Bt + C\binom{t}{2} = t^2. $$

Therefore the sum is equal to
$$ \binom{n+1}{2} + 2\binom{n+1}{3}. $$