Share
Explore BrainMass

Binomial[2n, n] = Sum from k=0 to n of Binomial[n,k]^2

Prove that (2n choose n) = the sum from k=0 to n of (n choose k) squared.

Solution Preview

Consider a set S of 2N objects (e.g. the numbers 1, 2, 3,..., 2N). Then there are Binomial[2N,r] ways to choose r objects from this set. You can easily prove that in general Binomial[R,r] is the number of ways to choose r objects out of R, using the fact that there are n! ways to rearrange n objects. All possible ways to choose r objects can be realized by putting the R objects in some order and then taking the first r objects. The total number of ways you can put the list of R objects in some arbitrary order is R!. The total number of ways for a fixed ...

Solution Summary

We give combinatorial proof of the identity Binomial[2n, n] = Sum from k=0 to n of Binomial[n,k]^2

$2.19