3
$\begingroup$

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.

  • 0
    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?2012-09-07

1 Answers 1

3

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

  • 0
    This is what I was looking for. Thank you. And you are correct about the combinatorial argument.2012-09-07