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.


  • $\begingroup$ 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. $\endgroup$ – 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} $$

  • $\begingroup$ 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$ $\endgroup$ – 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 $\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) $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.