Any probability experts??

Question

a) Prove that

(2n choose n) = summation from k = 0 to n (n choose k)^2

b) Show that for n > 0,

summation from i = 0 to n (-1)^i times (n choose i ) = 0

Hint: Use binomial theorem

Can anyone help me out with these proofs??

thank you!

Answer 1

A) If we want to choose n out of 2n objects, it is equivalent to selecting k out of the first n objects, and (n - k) out of the second n.  Thus, to find out the total number of ways of doing this, we simply need to sum over all possible k.  This gives us that

(2n choose n) = Σ(n choose k)(n choose (n-k))

But the combination function is symmetric in that (n choose k) = (n choose (n-k)).  So

(2n choose n) = Σ(n choose k)(n choose k) = Σ(n choose k)^2

Unfortunately I couldn't work out a more mathematically rigorous way of doing that.

B) Look at (1 - 1)^n.  1 - 1 = 0, so the whole expression must evaluate to 0.  However, by binomial theorem,

(1 - 1)^n = (nC0) * 1^n * (-1)^0 + (nC1) * 1^(n-1) * (-1)^1 + ... + (nCn) * 1^0 * (-1)^n

= nC0 - nC1 + nC2 + ... + (-1)^n * nCn

=ΣnCi * (-1)^i over i.