Closed formula for linear binomial identity

Question

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!

Answer 1

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} $$

Answer 2

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) $$

Answer 3

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.