0
$\begingroup$

Prove for for all $n\in \mathbb{N}$: $\sum_{l=0}^{n}\binom{n}{l}=2^{n}$

I know the steps of induction but i have no idea how to prove this equation with binomial coefficient.

1) For the induction base i need to take one number and it should be $n=1$. So, do i use this value $n$ for both $n$ and $l$ in the equation? In that case i believe that equation is not valid.

2) Should i for inductive claim increase both $n+1$ and $l+1$?

$\endgroup$
  • 4
    $\begingroup$ Are you allowed to use the binomial theorem? $\endgroup$ – carmichael561 Jul 23 '16 at 17:34
  • $\begingroup$ Technically, for the induction you may want to use $n=0$ as base case. $\endgroup$ – Clement C. Jul 23 '16 at 17:49
  • $\begingroup$ Also, see this page 5/6 of this document for three proofs: Link $\endgroup$ – FraGrechi Jul 23 '16 at 17:57
1
$\begingroup$

Since the meat of your question seems to be about how to prove this claim with induction (even though the other answers provide much shorter and easier proofs), that is how I will choose to approach.


Checking base case: Here, we check that the statement is true for some starting value(s) of $n$. The statement's truth will depend only upon $n$ as $l$ is only used as a shorthand here to make the sum easier to write ($l$ will range between all values from $0$ to $n$ and will not be a specific single number in general)

If you consider $0\in\Bbb N$, we start with the base case of checking if $\sum\limits_{l=0}^0\binom{0}{l}=\binom{0}{0}=\frac{0!}{0!0!}=1=2^0$, so the base case is valid.

Otherwise, for $n=1$ we check that $\sum\limits_{l=0}^1\binom{1}{l}=\binom{1}{0}+\binom{1}{1}=1+1=2=2^1$, so the base case is again valid.


Inductive step: Again, $l$ will be all possible values in the range, so we do not change how $l$ appears in the inductive step. We assume that the statement $2^n = \sum\limits_{l=0}^n \binom{n}{l}$ is true for some $n$ and we wish to prove that from this it follows that it is true for the next value, $n+1$.

Here, we rely on something known as pascal's identity: $\binom{n+1}{r} = \binom{n}{r}+\binom{n}{r-1}$.

Examining the case of $n+1$, we have then:

$$\begin{array}{rlr}\sum\limits_{l=0}^{n+1}\binom{n+1}{l}&=\sum\limits_{l=0}^{n+1}\left(\binom{n}{l}+\binom{n}{l-1}\right)&\text{via pascal's identity}\\ &=\left(\sum\limits_{l=0}^{n+1}\binom{n}{l}\right)+\left(\sum\limits_{l=0}^{n+1}\binom{n}{l-1}\right)&\text{by splitting into separate summations}\\ &=\left(\binom{n}{n+1}+\sum\limits_{l=0}^n\binom{n}{l}\right) + \left(\binom{n}{-1}+\sum\limits_{l=1}^{n+1}\binom{n}{l-1}\right)&\text{by breaking off last and first pieces respectively}\\ &=\left(\sum\limits_{l=0}^{n}\binom{n}{l}\right)+\left(\sum\limits_{l=0}^{n}\binom{n}{l}\right)&\text{broken off terms equalled zero and reindexing of right}\\ &=2^n+2^n&\text{by induction hypothesis}\\ &=2\cdot (2^n)=2^{n+1}&\text{by simplification}\end{array}$$

Hence, it follows that it is true for $n+1$ as well, therefore by induction the statement is true for all $n\in\Bbb N$.

$\endgroup$
  • $\begingroup$ And can you give me any hint how could I prove it easier, without induction? $\endgroup$ – Tars Nolan Jul 25 '16 at 11:31
1
$\begingroup$

If $S$ is a set with $n$ elements, then $\binom{n}{l}$ is the number of subsets of $S$ with $l$ elements.

$\sum_{l=0}^{n}\binom{n}{l}$ is then the number of all subsets of $S$ and this is equal to $2^{n}$ because the subsets of $S$ can be put into bijection with the set of $n$-bit strings.

$\endgroup$
1
$\begingroup$

For a prove by induction:

You can start the induction at $n=0$, which is trivial. So let $n$ be greater than $0$

This is actually needed in the calculations that follow, since we will use the induction hypothesis on $n-1$ which should not be smaller than $0$

\begin{align} \sum_{k=0}^{n} \binom{n}{k} &= 1+ \sum_{k=1}^{n-1} \binom{n}{k} + 1 \\ &= 1+ \sum_{k=1}^{n-1} \left[ \binom{n-1}{k-1} + \binom{n-1}{k} \right] + 1 \\ &= 1+ \sum_{k=1}^{n-1} \binom{n-1}{k-1} + \sum_{k=1}^{n-1}\binom{n-1}{k} + 1 \\ &= \sum_{k=1}^{n} \binom{n-1}{k-1} + \sum_{k=0}^{n-1}\binom{n-1}{k} \\ &=\sum_{k=0}^{n-1} \binom{n-1}{k} + \sum_{k=0}^{n-1}\binom{n-1}{k} \\ &= 2 \cdot \sum_{k=0}^{n-1} \binom{n-1}{k} = 2\cdot 2^{n-1} \end{align} In the last step the induction hypothesis was used.

$\endgroup$
0
$\begingroup$

The binomial coefficient $n\choose i$ is by definition, the coefficient of $x^i$ in the expanded binomial $(1+x)^n$, i.e., $(1+x)^n=\sum_{i=0}^n{n\choose i}x^i$. Use this definition with $x=1$.

$\endgroup$
  • $\begingroup$ I don't think I've ever seen $\binom{n}{i}$ defined that way. The definition $\binom{n}{i} = |\{ A \subseteq \{ 1, 2, \dots, n \} : |A|=i \}|$ is far more common, in which case there is more work to be done. The definition $\binom{n}{i} = \frac{n!}{i!(n-i)!}$ is (abhorrent but) also common (when $i \le n$). $\endgroup$ – Clive Newstead Jul 23 '16 at 18:10
0
$\begingroup$

Yeah if you use binomial theorem ..then $$\sum_{l=0}^{n} nC_l=^nC_0+^nC_1+^nC_2+...... $$ Which is equal to $$1+ ^nC_1+^nC_2+....+^nC_n $$ That is $(1+1)^n$ ...taking x=1and a=1 in the expansion of $(x+a)^n$

$\endgroup$

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