Welcome to our community

Be a part of something great, join today!

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

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Jameson

Administrator
Staff member
Jan 26, 2012
4,043
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$


Remember to read the POTW submission guidelines to find out how to submit your answers!
 
Last edited:
  • Thread starter
  • Admin
  • #2

Jameson

Administrator
Staff member
Jan 26, 2012
4,043
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

[tex]{n\choose r} \ + \ {n\choose r - 1} \ = \ {n + 1 \choose r + 1}[/tex]



[tex]Note: \ \ \ {n \choose 0} \ = \ {n + 1 \choose 0}[/tex]

[tex] \ \ and \ \ \ \ \ \ {n \choose n } \ = \ {n + 1 \choose n + 1}[/tex]


Base case for mathematical induction:

[tex]2^0 \ = {n\choose 0} \ = \ 1[/tex]

So the base case is true.


Assume:

[tex] \ \ \ \ 2^n \ = \ \ \ \ \ {n\choose 0} \ \ \ \ \ \ + \ \ \ \ {n \choose 1} \ \ + \ \ \ \ {n \choose 2} \ \ \ \ + \ ... \ + \ \ {n\choose n - 2} \ + \ \ \ {n \choose n - 1} \ \ + \ \ \ \ \ \ {n \choose n}[/tex]


[tex] + \ \ 2^n \ = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {n \choose 0} \ \ + \ \ \ \ \ {n \choose 1} \ \ \ + \ ... \ + \ \ \ {n\choose n - 3} \ + \ \ \ {n \choose n - 2} \ + \ \ \ \ {n \choose n - 1} \ \ + \ \ \ {n \choose n} [/tex]
_________________________________________________________________________________________________

[tex]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}[/tex]




The base case, combined with the assumption for the expression for [tex] \ 2^n[/tex],
was used above to show that the expression for [tex] \ 2^{n + 1}[/tex] follows.


Thus, by the Principle of Mathematical Induction, the original proposition is true.
 
Last edited:
Status
Not open for further replies.