# Problem of the week #4 - April 23rd, 2012

Status
Not open for further replies.

#### Jameson

Staff member
Thanks to Chris L T521 for helping with this one.

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

Hint:
Rewrite $2^n$

Last edited:

#### Jameson

Staff member
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.
$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}$

Alternate solution from caffeinemachine:

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.

Another alternate solution from checkittwice:

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.

Last edited:
Status
Not open for further replies.