11
$\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$
16
$\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$
9
$\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$
  • $\begingroup$ I'm not too sure what to do next $\endgroup$ – xyz Oct 9 '13 at 6:05
  • $\begingroup$ Sorry nevermind, it's simple ty $\endgroup$ – xyz Oct 9 '13 at 6:18
  • $\begingroup$ @PrahladVaidyanathan what is the step ${n+1 \choose 1} = {n \choose 1} + {n \choose 1}$ $\endgroup$ – bodokaiser Mar 15 '15 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.