How Does the Sum of Binomial Coefficients Equal \(2^n\)?

[Jameson]

Thanks to Chris L T521 for helping with this one.

If $n$ is a positive integer, show that [math]{n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n[/math]

Hint:
[sp]Rewrite $2^n$[/sp]

 

[Jameson]

Congratulations to the following members for their correct solutions:

1) Sudharaka
2) caffeinemachine
3) checkittwice

Solution:

This is the solution Chris L T521 was looking for when he wrote the problem.
[sp]\[2^n=(1+1)^n=\sum_{i=0}^{n}{n\choose i}1^{i}=\sum_{i=0}^{n}{n\choose i}={n\choose 0}+{n\choose 1}+\cdots+{n\choose n}\][/sp]

Alternate solution from caffeinemachine:

[sp]Consider a set $S$ of $n$ distinct objects. We count how many distinct subsets of $S$ are there.

we can choose 0 elements subset, or a 1 element subset, or a 2 element subset, ..., or an $n$ element subset.
There is no overlap amongst the $n+1$ cases listed above .

So total number of disctinct subsets of $S$ are $ {n \choose 0} +{ n \choose 1} + \ldots + {n \choose n}$.

Another way of counting the number of distinct subsets of $S$ is:
Consider the elements of $S$ one by one. One can either select an element or reject it. There are hence $2^n$ distinct subsets of $S$.

The required result is now immediate.[/sp]

Another alternate solution from checkittwice:

[sp]It can be shown with algebra that

$${n\choose r} \ + \ {n\choose r - 1} \ = \ {n + 1 \choose r + 1}$$
$$Note: \ \ \ {n \choose 0} \ = \ {n + 1 \choose 0}$$

$$\ \ and \ \ \ \ \ \ {n \choose n } \ = \ {n + 1 \choose n + 1}$$Base case for mathematical induction:

$$2^0 \ = {n\choose 0} \ = \ 1$$

So the base case is true.Assume:

$$\ \ \ \ 2^n \ = \ \ \ \ \ {n\choose 0} \ \ \ \ \ \ + \ \ \ \ {n \choose 1} \ \ + \ \ \ \ {n \choose 2} \ \ \ \ + \ ... \ + \ \ {n\choose n - 2} \ + \ \ \ {n \choose n - 1} \ \ + \ \ \ \ \ \ {n \choose n}$$$$+ \ \ 2^n \ = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {n \choose 0} \ \ + \ \ \ \ \ {n \choose 1} \ \ \ + \ ... \ + \ \ \ {n\choose n - 3} \ + \ \ \ {n \choose n - 2} \ + \ \ \ \ {n \choose n - 1} \ \ + \ \ \ {n \choose n}$$
_________________________________________________________________________________________________

$$2 \cdot2^n \ = \ {n + 1 \choose 0} \ + \ {n + 1 \choose 1} \ + \ {n + 1 \choose 2} \ + \ ... \ + \ \ {n + 1 \choose n - 2} \ \ + \ \ \ {n + 1\choose n - 1} \ \ + \ \ \ {n + 1 \choose n } \ \ + \ {n + 1 \choose n + 1} \ \ = \ \ \ 2^{n + 1}$$

The base case, combined with the assumption for the expression for $$\ 2^n$$,
was used above to show that the expression for $$\ 2^{n + 1}$$ follows.Thus, by the Principle of Mathematical Induction, the original proposition is true. [/sp]