Closed formula for linear binomial identity I have the following identity:
\begin{equation}
m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}
\end{equation}
I solved for the values and learned of the interpretation of W, X, Y, and Z in my last post:
Combinatorial reasoning for linear binomial identity
Now, I am interested in using the above to find a closed form solution for:
\begin{equation}
\sum\limits_{k=1}^nk^4 \\
\end{equation}
I do not see how to get a closed form solution to the above sum. What steps can I take? I especially would like to use the work from my last post.
Thanks!
 A: Hint:
$$\sum_{m=1}^n\binom{m}{r}=\sum_{m=1}^n \left[\binom{m+1}{r+1}-\binom{m}{r+1}\right]$$
Now use the method of differences.
A: Use the identity
$$
\sum_{j=0}^{k-m}\binom{k-j}{m}\binom{j}{n}=\binom{k+1}{m+n+1}
$$
setting $m=0$ to get
$$
\sum_{j=0}^{k}\binom{j}{n}=\binom{k+1}{n+1}
$$
Then, once we have that
$$
m^4=24\binom{m}{4}+36\binom{m}{3}+14\binom{m}{2}+1\binom{m}{1}+0\binom{m}{0}
$$
we get that
$$
\begin{align}
\sum_{m=1}^k m^4
&=24\binom{k+1}{5}+36\binom{k+1}{4}+14\binom{k+1}{3}+1\binom{k+1}{2}+0\binom{k+1}{1}\\
&=24\binom{k}{5}+60\binom{k}{4}+50\binom{k}{3}+15\binom{k}{2}+1\binom{k}{1}+0\binom{k}{0}
\end{align}
$$
A: If $r>1$:
$\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r
\end{array}\right)=\sum_{k=1}^{n}\left(\begin{array}{c}
k-1\\
r
\end{array}\right)+\sum_{k=1}^{n}\left(\begin{array}{c}
k-1\\
r-1
\end{array}\right)=\\
=\sum_{k=0}^{n-1}\left(\begin{array}{c}
k\\
r
\end{array}\right)+\sum_{k=0}^{n-1}\left(\begin{array}{c}
k\\
r-1
\end{array}\right)=\\
=\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r
\end{array}\right)-\left(\begin{array}{c}
n\\
r
\end{array}\right)+\left(\begin{array}{c}
0\\
r
\end{array}\right)+\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r-1
\end{array}\right)-\left(\begin{array}{c}
n\\
r-1
\end{array}\right)+\left(\begin{array}{c}
0\\
r-1
\end{array}\right)=\\
=\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r
\end{array}\right)-\left(\begin{array}{c}
n\\
r
\end{array}\right)+\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r-1
\end{array}\right)-\left(\begin{array}{c}
n\\
r-1
\end{array}\right)=\\
=\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r
\end{array}\right)+\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r-1
\end{array}\right)-\left(\begin{array}{c}
n+1\\
r
\end{array}\right)
 $ 
$\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r
\end{array}\right)=\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r
\end{array}\right)+\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r-1
\end{array}\right)-\left(\begin{array}{c}
n+1\\
r
\end{array}\right)
  $
$\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r-1
\end{array}\right)=\left(\begin{array}{c}
n+1\\
r
\end{array}\right)
 $
Or $\sum_{k=1}^{n}\left(\begin{array}{c}
k\\
r
\end{array}\right)=\left(\begin{array}{c}
n+1\\
r+1
\end{array}\right) 
 $ (for $r>0$)
So, if $\begin{equation}
m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}
\end{equation}$ then $\sum_{k=1}^{n}k^{4}=X\left(\begin{array}{c}
n+1\\
5
\end{array}\right)+Y\left(\begin{array}{c}
n+1\\
4
\end{array}\right)+Z\left(\begin{array}{c}
n+1\\
3
\end{array}\right)+W\left(\begin{array}{c}
n+1\\
2
\end{array}\right)
 $
I remember it from book http://en.wikipedia.org/wiki/Concrete_Mathematics, where Knuth and Co did the same thing what you want to do now.
Also I suggest related book $A=B$ (about summing of hypergeometric sums) which can be legally downloaded here - http://www.math.upenn.edu/~wilf/Downld.html

So, if I got it right, then in general case
$$\sum_{k=1}^{n}k^{m}=\sum_{k=1}^{m}k!\left\{ \begin{array}{c}
m\\
k
\end{array}\right\} \left(\begin{array}{c}
n+1\\
k+1
\end{array}\right)
 $$
