<s>[INST] Proving formula for sum of squares with binomial coefficient $$\sum_{k=0}^{n-1}(k^2)= \binom{n}{3} + \binom{n+1}{3}$$
How should I prove that it is the correct formula for sum of squares?
Should I use induction to prove the basis? Any help is appreciated.
 [/INST] It's easy to prove this directly from the definition of the binomial coefficient. The advantage is you don't need to remember any binomial identities, or try to rewrite a fraction to look like a binomial.
The left-hand side is $$\sum_{k=0}^{n-1}k^2=\frac{n(n-1)(2n - 1)}{6}$$ by a well known formula (you can also prove this by induction very easily).
The right-hand side is $$\binom{n}{3} + \binom{n + 1}{3}=\frac{n!}{3!(n - 3)!} + \frac{(n + 1)!}{3!(n + 1 - 3)!} = \frac{n! \left(n - 2\right)! + \left(n - 3\right)! \left(n + 1\right)!}{6 \left(n - 3\right)! \left(n - 2\right)!}$$
Writing $n! = n(n - 1)(n - 2)(n - 3)!$ we can cancel $(n - 3)!$ giving $$\frac{n(n - 1)(n - 2) \left(n - 2\right)! +  \left(n + 1\right)!}{6 \left(n - 2\right)!}.$$ Similarly we can write $(n + 1)! = (n + 1)n(n - 1)(n - 2)!$ and cancel $(n -2)!$ giving $$\frac{n(n - 1)(n - 2) +  \left(n + 1\right)n(n - 1)}{6}.$$ Factoring $n(n - 1)$ in the numerator gives $$\frac{n(n - 1)(n - 2 + n + 1)}{6} = \frac{n(n - 1)(2n - 1)}{6}.$$
</s>