<s>[INST] 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!
 [/INST] 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)
 $$
</s>