Prove ∑ … = (2^n-1)n!

**tiny-tim** · Feb19-09, 08:39 AM

Prove, for any integer n:

$LaTeX Code: \\sum_{0\\,\\leq\\,m\\,< n/2}\\,(-1)^m(n - 2m)^n\\,^nC_m\\ =\\ 2^{n-1}\\,n!$

for example, 7⁷ - 5⁷7 + 3⁷21 - 1⁷35

= 823543 - 546875 + 45927 - 35 = 304560 = 64 times 5040

**Gokul43201** · Feb19-09, 08:57 AM

I'm guessing there is a brute force way to prove this as well as a clever combinatoric argument, and you're hoping we only find the first, so you can dazzle us with the second?

**tiny-tim** · Feb19-09, 10:55 AM

Originally Posted by Gokul43201

I'm guessing there is a brute force way to prove this as well as a clever combinatoric argument, and you're hoping we only find the first, so you can dazzle us with the second?

Hi Gokul!

Sort of … I accidentally found a geometric-cum-combinatoric proof of this while looking at a homework thread,

but I couldn't help thinking that there must be some way of solving this just by looking at it and coming up with a solution …

but no ordinary technique comes to mind since the exponand (is that the right word?

) keeps changing.

I was hoping somebody knew a finding-the-solution technique (maybe for a simpler problem), rather than an already-knowing-what the-solution-is technique!

**Count Iblis** · Mar24-09, 12:29 PM

Isn't this an exercise from this book:

http://www.math.upenn.edu/~wilf/AeqB.html