Combinations Proof

Question

Show that $2^n = \sum_{i=0}^n \binom ni$.

I tried expanding $\sum_{i=0}^n \binom ni$ into sum of: $\frac{n!}{(n-r)!r!}$, and found the common ratio and then used the sum formula, but I did not get to $2^n$.

Answer 1

HINT: Try expanding $2^n = (1+1)^n$ using the Binomial Formula. Do you notice any simularities between your problem and this expansion?

Answer 2

Using the identities

$$\begin{align*} \binom{n+1}{r} &= \binom{n}{r-1} + \binom{n}{r}&&(1\le r \le n)\\ \binom{n}0 &= \binom{n}{n} = 1 \end{align*}$$

and prove by induction that your result is true for all integers $n\ge 0$:

$$ \sum^{n+1}_{r=0}\binom{n+1}{r} = \binom{n+1}0 + \sum^{n}_{r=1}\binom{n+1}{r} + \binom{n+1}{n+1} $$

Answer 3

Consider the expansion of $(x+1)^n$. This looks like: $$ x^n + nx^{n-1} + \cdots + nx + 1$$

So how do we get the coefficients of the intermediate terms? They are just the number of different way to choose $k\; x$ terms (and $n-k\; 1$ terms) out of the $n$ brackets $(x+1)\cdots(x+1)$. So $$(x+1)^n = \sum_{k=0}^n{n \choose k}x^k$$

Now set $x=1$.

Answer 4

Well, you also just use induction over $n$, so $$ 2^n = \sum_{i=0}^n \binom ni \tag1 $$ clearly holds for $n=1$ (or even for $n=0$), since $$ 2^1=\sum_{i=0}^1 \binom 1i=\binom 10+\binom11=1+1=2 $$ Now we want to show that $$ 2^{n+1} = \sum_{i=0}^{n+1} \binom {n+1}i $$ holds by using our assumption $(1)$. We have by using the Pascal identity $$ {n \choose k}={n-1 \choose k-1}+{n-1 \choose k} $$ to show the following $$ 2^{n+1}=\sum_{i=0}^{n+1} \binom {n+1}i=1+\sum_{i=1}^{n} \bigg(\binom {n}{i-1}+\binom {n}{i}\bigg)+1 $$ which gives us \begin{align} 1+\sum_{i=1}^{n} \binom {n}{i-1}+\sum_{i=1}^{n}\binom {n}{i}+1&=\binom nn+\sum_{i=1}^{n} \binom {n}{i-1}+\sum_{i=1}^{n}\binom {n}{i}+\binom n0\\ &=\sum_{i=1}^{n+1} \binom {n}{i-1}+\sum_{i=0}^{n}\binom {n}{i}\tag 2\\ &=\sum_{i=0}^{n} \binom {n}{i}+\sum_{i=0}^{n}\binom {n}{i}=2^n+2^n=2^{n+1} \tag3 \end{align} while we used an index shift in $(2)$ and our induction assumption in $(3)$. So we eventually proved by induction $$ 2^n = \sum_{i=0}^n \binom ni $$

Answer 5

Method 1: Use binomial theorem

$$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$

Choose $$x=y=1$$ to get

$$(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k 1^{n-k}$$

---

Method 2: Use induction

1. Prove $$2^0 = \sum_{k=0}^{0} \binom{0}{k}$$

2. Prove for n=1,2,...

$$2^{n-1} = \sum_{k=0}^{n-1} \binom{n}{k} \to 2^n = \sum_{k=0}^{n} \binom{n}{k}$$

This comes down to proving

$$2\binom{n-1}{0} + ... + 2\binom{n-1}{n-1} = \binom{n}{0} + ... + \binom{n}{n}$$

---

Method 3: Use counting argument

Consider creating a sandwich having to decide which of $n$ items you're going to include.

Say item 1 is lettuce. item 2 is tomato. item 3 is patty. item 4 is ketchup and so on until item n is cheese.

You could go through each item and decide whether or not to add it (2 choices per item). By the multiplication rule of counting, the number ways to do this is $2^n$.

That's the LHS. As for the RHS,

you can choose none out of the n items. You can choose one of the n items. You can choose two of the n items. So on until you can choose n of the n items.

Since these are mutually exclusive cases, by the addition rule of counting, the number of ways to do this is:

$$\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n}$$