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.

How do I prove the following identity:

$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$

I am trying to use inclusion-exclusion, and this will boil down to a sum like inclusion-exclusion, and the $\binom{2n-2k}{n-1}$ term wouldn't matter (it will be equivalent to set sizes). Is this a correct way to go?

share|improve this question
1  
similar: math.stackexchange.com/questions/94514/… –  ulead86 Dec 17 '12 at 12:23
    
@ulead86: How is that related? –  joriki Dec 17 '12 at 12:24
    
I tried reading that - didn't seem like the same question in first look. –  Mark Dec 17 '12 at 12:24
    
sorry, changed the link (wrong copy+paste) –  ulead86 Dec 17 '12 at 12:25
1  
@ulead86: Unfortunately the new link seems just as unrelated as the other one. –  joriki Dec 17 '12 at 12:27
add comment

2 Answers

up vote 5 down vote accepted

In how many ways can you select $m\lt n$ squares on a $2\times n$ board such that exactly $n$ columns contain a selected square?

[Edit:]

From the lack of upvotes and the inquiring comment of a distinguished user I conclude that I should explain this perhaps overly laconic answer.

The OP wanted to prove the result by inclusion–exclusion. The number of ways to select $m$ squares on a $2\times n$ board such that at most $j$ particular columns contain a selected square is $\binom{2j}m$. By inclusion–exclusion, if there are $a_j$ ways to do something with at most $j$ particular objects, then there are

$$ \sum_{k=0}^n(-1)^k\binom nka_{n-k} $$

ways to do it with exactly $n$ objects (where the binomial coefficient counts the number of ways of selecting $n-k$ particular ones of the $n$ objects). Putting this together yields the number of ways to select $m$ squares on a $2\times n$ board such that exactly $n$ columns contain a selected square:

$$ \sum_{k=0}^n(-1)^k\binom nk\binom{2n-2k}m\;. $$

Since it's impossible to have exactly $n$ columns contain a selected square if less than $n$ squares are selected, this is $0$ for $m\lt n$, and thus in particular for $m=n-1$.

share|improve this answer
    
I can answer that question easily (the answer is indeed equal to the right hand side of the equation in the original question), but I fail to see what this weird description has to do with the (more interesting) left hand side. Notably there is nothing alternating in your description. –  Marc van Leeuwen Dec 17 '12 at 15:59
    
@Marc: Sorry for being overly brief; I thought this would work as a hint, but apparently it didn't; I've spelled it out. –  joriki Dec 17 '12 at 16:36
add comment

The function $g:k\mapsto \binom{2n-2k}{n-1}$ is a polynomial function of degree $n-1$. The operation $f\mapsto\bigl(x\mapsto\sum_{k=0}^n(-1)^k\binom knf(x+k)\bigr)$ equals $(-1)^n\Delta^n$, where $\Delta$ is the finite difference operator $f\mapsto\bigl(x\mapsto f(x+1)-f(x)\bigr)$, which kills constant functions and lowers the degree of polynomial functions by $1$. Therefore $(-1)^n\Delta^n(g)=0$, which means that $$ x\mapsto\sum_{k=0}^n(-1)^k\binom kng(x+k) $$ is the zero function. Now apply for $x=0$ to obtain $$ 0=\sum_{k=0}^n(-1)^k\binom kng(k) = \sum_{k=0}^n(-1)^k\binom kn\binom{2n-2k}{n-1}. $$

share|improve this answer
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.