binomial Sum.

[man111]

Prove that [tex]C(n,0).C(n,0) - C(n+1,1).C(n,1) + C(n+2,2).C(n,2)......................... = (-1)^n[/tex]

Where [tex]C(n,r) =[/tex] Selection of [tex]r[/tex] things out of [tex]n[/tex] things.

[mkmarinov]

Doesn't the sum end at some point?

[man111]

Yes last term is [tex](-1)^n.C(n+n,n).C(n,n)[/tex]

[mkmarinov]

I am pretty sure this could be solved with the appropriate generating function.

[man111]

mkmarinov can you solve here.

[drago]

I think one of the most interesting problems You have ever posted here!

Let [tex]S= \sum_{j=0}^{j=n}(-1)^j C^j_n C^j_{n+j}[/tex]
[tex]S_1= \sum_{j=0}^{j=n}(-1)^j C^j_n C^{n-j}_{n+n-j}[/tex]
It is not difficult to see that:
(1) [tex]S=S_1.(-1)^n.[/tex] For example:
[tex]2S=\sum_{j=0}^{j=n}[ (-1)^j C^j_n C^j_{n+j} + (-1)^{n-j}C^{n-j}_n C^{n-j}_{n+n-j} ]=
\sum_{j=0}^{j=n}[ (-1)^n(-1)^{n-j}C^{n-j}_n C^j_{n+j} + (-1)^n(-1)^j C^j_n C^{n-j}_{n+n-j} ]
=(-1)^n 2 S_1.[/tex]
Now let [tex]P(x)=\frac{(x+1)(x+2)...(x+n)}{n!}.[/tex] [tex]P[/tex] is of degree n.
Then [tex]P(j)=C^j_{n+j}, j=0,1,...,n.[/tex]
So: [tex]S=\sum_{j=0}^{j=n}(-1)^j C^j_n P(j)= (-1)^n \sum_{j=0}^{j=n}(-1)^j C^j_n P(n-j)[/tex], due to (1).
Now we are using the fact that if [tex]P(x)[/tex] is of degree n(or less) [tex]\sum_{j=0}^{j=n}(-1)^j C^j_n P(n-j) = n!a_n[/tex]
where [tex]a_n[/tex] is the coefficient of degree n in P(x).
(see http://en.wikipedia.org/wiki/Binomial_coefficient , (13b) )

In our case: [tex]a_n=\frac{1}{n!}[/tex]
Finally [tex]S=(-1)^n.[/tex]

[man111]

Thanks drago for one of the best ever solution.

[drago]

I would appreciate if You share the original solution, or a sulution based on a different idea.