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.
 A: You can also derive this using discrete calculus. Let $x^{\underline{n}} = x(x-1)(x-2)...(x - n + 1)$ be the falling factorial. We also define the discrete derivative as $\Delta f(n) = f(n+1) - f(n)$. Notice that this is the difference quotient from continuous calculus, but with integers instead. So $\Delta x^{\underline{n}} = nx^{\underline{n-1}}$. That looks just like $\frac{d}{dx} x^{n} = nx^{n-1}$, right?
So what we are really doing is taking a discrete integral, which is a summation. The fundamental theorem of discrete calculus is analogous to the fundamental theorem of calculus.
So the fundamental theorem of discrete calculus says:
$$\sum_{x=a}^{b-1} x^{\underline{i}} = \frac{b^{\underline{i+1}} - a^{\underline{i+1}}}{i+1}$$
This is analogous to saying that $\int_{a}^{b} f(x) dx = F(b) - F(a)$, which is the fundamental theorem of calculus.
Now, we will rewrite your summation in terms of falling factorials. So $k^{2} = k^{\underline{2}} + k^{\underline{1}} = k(k-1) + k$. And we consider:
$$\sum_{i=0}^{n-1} (k^{\underline{2}} + k^{\underline{1}}) = \frac{1}{3}n^{\underline{3}} + \frac{1}{2}n^{\underline{2}} = \frac{n(n-1)(n-2)}{3} + \frac{n(n-1)}{2}$$
Now we do some algebra to simplify:
$$\frac{n(n-1)(n-2) + n(n-1)(n-2) + 3n(n-1)}{6} = \binom{n}{3} + \frac{n(n-1)(n-2) + 3n(n-1)}{6} = \binom{n}{3} + \binom{n+1}{3}$$
Note: In the general case, we can write, where $S(n, k)$ denotes the Stirling Number of the Second kind:
$x^n = \sum_{i=0}^{n} S(n, k) x^{\underline{k}}$
A: Using repeated differences we get
$$
\begin{array}{llll}
0 & 1 & 5 & 14 & \\
1 & 4 & 9 & \\
3 & 5 & \\
2& \\
\end{array}
$$
The last difference repeats forever, because $k^2$ has degree $2$.
Newton's interpolation formula then gives us this formula for the sequence of sums:
$$
0 \binom{n-1}{0} + 1 \binom{n-1}{1} + 3 \binom{n-1}{2} + 2 \binom{n-1}{3}
$$
Using Pascal's rule repeatedly we get
$$
\binom{n-1}{1} + \binom{n-1}{2} + \binom{n-1}{2} +  \binom{n-1}{2} + \binom{n-1}{3} + \binom{n-1}{3}
$$
$$
=\binom{n}{2} + \binom{n-1}{2} + \binom{n}{3} + \binom{n-1}{3}
$$
$$
=\binom{n}{2} + \binom{n}{3} + \binom{n-1}{2} + \binom{n-1}{3}
$$
$$
=\binom{n+1}{3} + \binom{n}{3}
$$
A: First, write
$$k^2=2{k\choose2}+{k\choose1}$$
Thus,
$$\sum_{k=0}^n k^2=2\sum_{k=0}^n {k\choose2}+\sum_{k=0}^n {k\choose1}$$
Now, use the formula (see here for a proof)
$$\sum_{k=0}^n {k\choose p}={n+1 \choose p+1}$$
Therefore,
$$\sum_{k=0}^n k^2=2{n+1 \choose 3}+{n+1 \choose 2}={n+1 \choose 3}+{n+1 \choose 3}+{n+1 \choose 2}={n+1 \choose 3}+{n+2 \choose 3}$$
Or, shifting by $1$,
$$\sum_{k=0}^{n-1} k^2={n+1 \choose 3}+{n \choose 3}$$
A: Yes you can. Base case is easy. After it, you have to prove following implication.
$$\left(\underbrace{\sum_{k=0}^{n-1}(k^2)= \binom{n}{3} + \binom{n+1}{3}}_{\mathrm{Assumption}}
\right) \Longrightarrow \left(
\underbrace{\sum_{k=0}^{n}(k^2)= \binom{n+1}{3} + \binom{n+2}{3}}_{\mathrm{Thesis}}
\right)
$$
Now, using assumption transform thesis.
$$\begin{split}
\sum_{k=0}^{n}(k^2) 
= n^2 + \sum_{k=0}^{n-1}(k^2) 
&=  n^2 + \binom{n}{3}+\binom{n+1}{3}\\
&= n^2 + \frac{n!}{3!\cdot (n-3)!} +\binom{n+1}{3}\\
&=n^2 + \frac{n \cdot (n-1) \cdot (n-2)}{6} + \binom{n+1}{3}\\
&=\frac{6n^2 + \left(n^3-3n^2+2n\right)}{6}+ \binom{n+1}{3}\\
&=\frac{n(n+1)(n+2)}{3!}+ \binom{n+1}{3}\\
&=\frac{(n+2)!}{3! \cdot \left((n+2)-3\right)!}+ \binom{n+1}{3}\\
&= \binom{n+2}{3} + \binom{n+1}{3}
\end{split}$$
$\mathscr{Q.E.D.}$
A: 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}.$$
