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.

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|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
add comment

1 Answer

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|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
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.