Can you prove that nC0 nC1 nC2 nCn2n?

Answer 1

Consider a set, S, consisting of n elements.

Then the number of subsets of S containing r objects is equal to the number of ways of choosing r elements out of n = nCr.Therefore

nC0 + nC1 + nC2 + ... + nCn is the total number of subsets of S.

Now consider each subset of S. Each element of S can either be in the subset or not in the subset. So for each element there are two choices. Therefore, n elements give 2^n possible subsets.

Since these are two different approaches to the total number of subsets of S,

nC0 + nC1 + nC2 + ... + nCn = 2^n.