Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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