# I am trying to prove the identity $\sum_{k=m}^{n} k^{\downarrow m }{n \choose k} = n^{\downarrow m } 2^{n-m}$

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.

-
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

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