# Closed formula for linear binomial identity

I have the following identity:

$$m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}$$

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: $$\sum\limits_{k=1}^nk^4 \\$$

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!

-
I was momentarily puzzled when I saw the words "closed form solution". Then I realized you meant "closed-form expression". One solves a problem or solves an equation. One does not "solve" an expression. One might evaluate it (seeking a value, not a "solution"), or one might seek another expression for it. But "solution" is not the right word here. –  Michael Hardy Feb 10 '13 at 22:41

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}

-
Awesome! The less general identity given in the second line is actually in my book and is used to show the sum of the first n integers when $n=1$ –  CodeKingPlusPlus Feb 11 '13 at 2:35

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.

-

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 $$$m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}$$$ 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)$$

-
@CodeKingPlusPlus I hope you like general case formula. ;) –  zaarcis Feb 11 '13 at 0:13
Your general case formula is correct. A reference is p. 199 of Rosen, Handbook of Discrete and Combinatorial Mathematics. –  Mike Spivey Feb 11 '13 at 17:56