Why does $2+{{n}\choose{1}}+{{n}\choose{2}}+\ldots+{{n}\choose{n-1}}=(1+1)^n$

Question

$${{n}\choose{0}}+ {{n}\choose{1}}+{{n}\choose{2}}+\ldots+{{n}\choose{n-1}}+{{n}\choose{n}}=(1+1)^n$$

I don't see why this is true, because (if I'm not mistaken)

\begin{align}&{{n}\choose{0}}+ {{n}\choose{1}}+{{n}\choose{2}}+\ldots+{{n}\choose{n-1}}+{{n}\choose{n}}\\&=1+{{n}\choose{1}}+{{n}\choose{2}}+\ldots+{{n}\choose{n-1}}+1\\ &=2+{{n}\choose{1}}+{{n}\choose{2}}+\ldots+{{n}\choose{n-1}} \end{align}

So my question is why

$$2+{{n}\choose{1}}+{{n}\choose{2}}+\ldots+{{n}\choose{n-1}}=(1+1)^n\;\;\;\;\text{(1)}$$

If anyone requires any context, I am reviewing some set theory, and I came across the proof that the power set of a set $S$ with $n$ elements had $2^{n}$ elements. Just to reiterate, I'm not looking for a proof of the cardinality of the power set. I just want to know, algebraically, why $(1)$ is true.

Thanks.

Answer 1

There is an easy way to prove the formula.

Suppose you want to buy a burger and you have a choice of 6 different condiments for it - mustard, mayonnaise, lettuce, tomatoes, pickles, and cheese. How many ways can you choose a combination of these condiments for your burger?

Of course, you can choose either 6 different condiments, 5 different condiments, 4 different condiments, etc. So the obvious way to solve the problem is:

$\begin{align}{{6}\choose{6}} + {{6}\choose{5}} + {{6}\choose{4}} + {{6}\choose{3}} + {{6}\choose{2}} + {{6}\choose{1}} = \boxed{64}\end{align}$

But there is a better way. Imagine 6 spaces for 6 condiments:

_____ _____ _____ _____ _____ _____

For every space, there are $2$ possible outcomes: Yes or No, meaning the condiment was chosen or the condiment was not chosen. With $2$ possible outcomes for each space, there are $2^6 = \boxed{64}$ possible ways.

We know that both ways have foolproof logic and will both give identical answers no matter how many condiments there are. So this means we have proven:

$\begin{align}\sum_{k = 0}^{n} \binom{n}{k} = 2^n\end{align}$

Answer 2

Binomial theorem!

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

Take $x=y=1$ to get your identity.

Answer 3

By the Binomial theorem, we have

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

So if we let $x = y = 1$, then we get your result.

The proof of the formula is traditionally done through induction. You also mentioned Pascal Triangles, hold your breath, because they are related. I suggest you look at the formula for small $n$, then examine the coefficients of the polynomial.

Answer 4

By the binomial theorem $(a+b)^n = \sum\limits_{i = 0}^{n} {{n}\choose{i}}a^{n-i}b^i$ If $a=b=1$

$(1+1)^n = \sum\limits_{i = 0}^{n}{{n}\choose{i}}$

So that $2 + \sum\limits_{i = 1}^{n-1}{{n}\choose{i}} = {{n}\choose{0}} + \sum\limits_{i = 1}^{n-1}{{n}\choose{i}} + {{n}\choose{n}} = \sum\limits_{i = 0}^{n}{{n}\choose{i}} = (1+1)^n $

Answer 5

Well it just follows from the general formula:

$(a+b)^n=\sum\limits_{k=0}^n \binom {n} {k}\,a^k\,b^{n-k}$,

which you can prove by induction see here .

Answer 6

The expression counts the number of subsets of a set with $n$ elements. There's a one-to-one correspondence between subsets of $\{1,\dots,n\}$ and $\{0,1\}^n$, given by assigning a subset $S$ to the tuple which has a $1$ at the $i$th component if $i \in S$. This gives you the count without applying the binomial theorem.

Answer 7

Combinatorially:

We are having a party and we have a list of $n$ people who we may or may not invite. We ask, "how many different possibilities of guests are there?" One way to arrive to an answer is saying, "We can invite no one and there is exactly $n \choose 0$ ways to do that, or we can invite one person and there are $n\choose 1$ ways to do that, ect." Following this logic we arrive at the left hand side. However, we want to double check our answer so we try another method. We say, "We can associate each person with the number $0$ if they are not invited and $1$ if they are. Therefore, each possible configuration is represented by a string of $0$s and $1$s of length $n$. Since each slot in this string has $2$ possibilities, we find that there are exactly $2^n$ distinct strings." This agrees with the right hand side. Since both (valid) methods were used to find an answer to this problem, we see that the left and right sides of the equation must agree.