Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove algebraically

$\sum_{k=m}^{n} k^{\downarrow m }{n \choose k} = n^{\downarrow m } 2^{n-m}$

I have an idea as to how to prove it when m = 1, but am having trouble otherwise.

When m=1, we just have

$\sum_{k=1}^{n} k^{\downarrow 1 }{n \choose k} = n^{\downarrow 1 } 2^{n-1} = n2^{n-1} $

I would appreciate any insight you guys could give would be appreciated. I do understand the identity combinatorially but am having issues with the algebra.

Longtime lurker, 1st time poster, so please forgive if I am not following proper protocol.

share|cite|improve this question
By $k^{\downarrow m}$ do you mean what I’d write as $k^{\underline m}=k(k-1)\dots(k-m+1)$, the falling $m$-th power? – Brian M. Scott Sep 7 '12 at 5:35
yes, you are correct – Lok Sep 7 '12 at 5:37
Can you elaborate on what "prove algebraically" means? Is a counting proof not acceptable? How about a power series based proof? – alex.jordan Sep 7 '12 at 5:40
Yes, a non-counting proof is required. I am not sure about a power series based proof, but I think that would be fine. – Lok Sep 7 '12 at 5:44
If you've got a counting proof, there are always ways to disguise it as an algebraic proof (the converse is harder). Why should you want to forbid counting proofs? – Marc van Leeuwen Sep 7 '12 at 8:47
up vote 3 down vote accepted

It’s the same basic calculation as for $m=1$, using the identity $k\binom{n}k=n\binom{n-1}{k-1}$ repeatedly:

$$\begin{align*} \sum_{k=m}^{n} k^{\downarrow m }{n \choose k}&=\sum_{k=m}^n\frac{k!n!}{(k-m)!k!(n-k)!}\\ &=\sum_{k=m}^n\frac{n!}{(k-m)!(n-k)!}\\ &=\sum_{k=m}^n\frac{n^{\downarrow m}(n-m)!}{(k-m)!(n-k)!}\\ &=n^{\downarrow m}\sum_{k=m}^n\binom{n-m}{k-m}\\ &=n^{\downarrow m}\sum_{k=0}^{n-m}\binom{n-m}k\\ &=n^{\downarrow m}2^{n-m}\;. \end{align*}$$

(But I think that the combinatorial argument gives more real insight!)

share|cite|improve this answer
This is what I was looking for. Thank you. And you are correct about the combinatorial argument. – Lok Sep 7 '12 at 5:50

Your Answer


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.