27
$\begingroup$

Prove by induction that for all $n \ge 0$:

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

In the inductive step, use Pascal’s identity, which is:

$${n+1 \choose k} = {n \choose k-1} + {n \choose k}.$$

I can only prove it using the binomial theorem, not induction.

$\endgroup$

4 Answers 4

33
$\begingroup$

For basic step n=0:
$\binom{0}{0}=\frac{0!}{0!0!}=2^0$

For induction step:
Let k be an integer such that $0\lt{k}$ and for all L, $0\le{L}\le{k}$ where $L\in{I}$, the formula stand true.
Then:
$$\binom{k}{0}+\binom{k}{1}+...+\binom{k}{k}=2^k$$
Now as can be illustrated easily $\binom{k}{0}=\binom{k+1}{0}$ and $\binom{k}{k}=\binom{k+1}{k+1}$.
Now by using Pascal's identity,
$$\begin{align}\binom{k+1}{0}+\binom{k+1}{1}+\binom{k+1}{2}+...+\binom{k+1}{k}+\binom{k+1}{k+1}\\=\binom{k+1}{0}+\binom{k}{0}+\binom{k}{1}+\binom{k}{1}+\binom{k}{2}+...+\binom{k}{k-1}+\binom{k}{k}+\binom{k+1}{k+1}\\=\binom{k}{0}+\binom{k}{0}+\binom{k}{1}+\binom{k}{1}+\binom{k}{2}+...+\binom{k}{k-1}+\binom{k}{k}+\binom{k}{k}\\=2*{\sum_{i=0}^k\binom{k}{i}}\\=2*2^k\\=2^{k+1}\end{align}$$ As the formula is also true for $k+1$ hence by second principle of finite induction this formula is valid for all integers greator than or equal to $0$.

$\endgroup$
16
$\begingroup$

Well, here it is : $$ \sum_{k=0}^{n+1} {n+1\choose k} = {n+1\choose 0 } + {n+1\choose 1 } + \ldots + {n+1\choose n } + {n+1\choose n+1} $$ $$ = 1 + {n\choose 0} + {n\choose 1} + {n\choose 1} + {n\choose 2 } + \ldots + {n\choose n-1} + {n\choose n} + 1 $$ $$ = {n\choose 0 } + {n\choose 0 } + {n\choose 1} + {n\choose 1 } + \ldots + {n\choose n-1} + {n\choose n-1} + {n\choose n} + {n\choose n} $$ $$ = 2 \times \sum_{k=0}^n {n\choose k } $$ Now induct!

$\endgroup$
3
  • $\begingroup$ I'm not too sure what to do next $\endgroup$
    – xyz
    Oct 9, 2013 at 6:05
  • $\begingroup$ Sorry nevermind, it's simple ty $\endgroup$
    – xyz
    Oct 9, 2013 at 6:18
  • $\begingroup$ @PrahladVaidyanathan what is the step ${n+1 \choose 1} = {n \choose 1} + {n \choose 1}$ $\endgroup$
    – bodokaiser
    Mar 15, 2015 at 9:59
12
$\begingroup$

In case anyone wants an alternative, from the binomial theorem,

$$(x+y)^n=\sum_{i=0}^{n}{n\choose i}x^{n-i}y^i$$

If we let $x=1$ and $y=1$, then $\sum_{i=0}^{n}{n\choose i}=2^n$.

$\endgroup$
4
$\begingroup$

Since someone decided to revive this 6 year old question, you can also prove this using combinatorics

Take n elements and count how many ways there are to put these two elements into 2 different containers (A and B)

a) Every element can take two states: it's either in A or in B. By one of the first theorems in combinatorics (the one about separating a task into steps), this gives n steps with 2 options at each step, so we get $2^n$

b) We can also think of adding up all the ways in which we can have k elements in A and n-k elements in B, for $0 \le k \le n$. For each k, this number is: "choose k elements that will go into A". Then the other n-k elements automatically go to B. So for each k this number is just ${n \choose k}$. Now, we add this for all k reviously mentioned to get $\sum_{k = 0}^n {n \choose k}$

And thus, $2^n = \sum_{k = 0}^n {n \choose k}$

$\endgroup$
3
  • $\begingroup$ Thinking about how many sets are in a power set could help , since ${n\choose k}$ represent the number of ways to construct a subset of size $k$. And the size of sets in a power set goes from $0$ to $n $ $\endgroup$
    – Milan
    Sep 24, 2019 at 16:52
  • $\begingroup$ While I totally agree that this is highly useful information that anyone seeing this identity for the first time should be aware of, the question did explicitly state that they were interested in an induction proof... $\endgroup$
    – JMoravitz
    Oct 8, 2019 at 12:30
  • 1
    $\begingroup$ The question is like 6 years old, I decided to post this answer after another user posted an alternative answer $\endgroup$ Oct 8, 2019 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .