# Prove by induction: $2^n = C(n,0) + C(n,1) + \cdots + C(n,n)$ [duplicate]

This is a question I came across in an old midterm and I'm not sure how to do it. Any help is appreciated.

$$2^n = C(n,0) + C(n,1) + \cdots + C(n,n).$$

Prove this statement is true for all $n \ge 0$ by induction.

-

## marked as duplicate by Marc van Leeuwen, Gigili, mau, Michael Albanese, MathOverviewJan 9 '14 at 10:59

So, what have you tried? What definition of the binomial coefficients are you using? – J. M. Aug 1 '12 at 2:09
Well I've tried this: 2^(k+1) = C(k+1, 0) + C(K+1, 1) ... C(K+1, K+1) – Jason Curt Aug 1 '12 at 2:13
Informally: Think of the right hand side as the number of subsets of a set of size $n$. If a set of size $n$ has $2^n$ subsets, how many subsets does a set of size $n+1$ have (think of the set of size $n$ with one additional element)? – David Mitra Aug 1 '12 at 2:14
You haven't answered my second question. What definition of the binomial coefficients are you using? Factorials? Recursion relation? Something else? – J. M. Aug 1 '12 at 2:24
To be honest I'm not quite sure since binomial coefficients weren't mentioned in the course – Jason Curt Aug 1 '12 at 2:55

Marvis's hint suffices. Anyways:

1. Base case at $n = 0$ is trivial to show: $2^0 = 1 = \dbinom{0}{0} = 1.$

2. Inductive hypothesis: assume $$2^k = \binom{k}{0} + \binom{k}{1} + \ldots + \binom{k}{k} \tag{1}$$

3. Inductive step: we need to show $$2^{k+1} \stackrel{?}{=} \binom{k+1}{0} + \binom{k+1}{1} + \ldots + \binom{k+1}{k+1} \tag{2}$$

From $(1),$ we have $$2^{k+1} = 2^k + 2^k = \\ \binom{k}{0} + \color{blue}{\binom{k}{0} + \binom{k}{1}} + \color{red}{\binom{k}{1} + \binom{k}{2}} + \ldots + \color{blue}{\binom{k}{k-1} + \binom{k}{k}} + \binom{k}{k}$$ Now group the colored terms using the identity $$\dbinom{k}{r-1} + \binom{k}{r} = \binom{k+1}{r}$$ We get $$2^{k+1} = \binom{k}{0} + \color{blue}{\binom{k+1}{1}} + \color{red}{\binom{k+1}{2}} + \ldots + \color{blue}{\binom{k+1}{k}} + \binom{k}{k}$$ Finally we use $$\binom{k}{0} = \dbinom{k+1}{0} = 1 \quad \text{and} \quad \binom{k}{k} = \dbinom{k+1}{k+1} = 1.$$ So $$2^{k+1} = \color{red}{\binom{k+1}{0}} + {\binom{k+1}{1}} + {\binom{k+1}{2}} + \ldots + {\binom{k+1}{k}} + \color{red}{\binom{k+1}{k+1}}. \square$$

-
BTW $\dbinom{x}{y} = C(x, y).$ – user2468 Aug 1 '12 at 2:57
Thanks for your help – Jason Curt Aug 1 '12 at 2:58
OP has accepted this answer, so apparently he knows of the recursion relation for the binomial coefficients. I had been asking what definition he was using since it can be either be proven from the factorial definition, or used as a definition in its own right, and it is unclear where OP is starting from... – J. M. Aug 1 '12 at 3:02
@J.D.: Please can you explain why $2^{k+1}=2^{k}+2^{k}$? – Hassan Muhammad Aug 1 '12 at 5:11
@HassanMuhammad $2^{k+1}=2 \times 2^k=2^k+2^k$ – Mark Bennet Aug 1 '12 at 5:43

HINT

You have $$2^k = \dbinom{k}{0} + \dbinom{k}{1} + \dbinom{k}{2} + \cdots + \dbinom{k}{k}$$ Multiply the above by $2$, rearrange terms and make use of $$\dbinom{k+1}{r} = \dbinom{k}{r} + \dbinom{k}{r-1}$$

-
Thanks for your help – Jason Curt Aug 1 '12 at 2:58

Well, $$(1+x)^n=\sum\limits_{i=0}^{n} \binom{n}{i}x^i.$$

Substituting $x=1$ gives the desired conclusion.

-
This is one of the easiest proofs, but OP was asking for an inductive route... – J. M. Aug 1 '12 at 2:14

The binomial coefficients can be read off the rows of Pascal's Triangle. Suppose the relationship is established for the $n$th row. The next row is obtained by adding adjacent numbers from the $n$th row, with a leading and trailing zero imagined. Each element of the $n$th row is used twice (with one zero at each end ...). Therefore the total doubles each time you go down a row. Base case is a total of 1 (row zero). This can be made equivalent to other answers - the mathematics is in showing that the binomial coefficients can be read off Pascal's Triangle.

-

Other people have given good answers, but I'd like to offer a simple intuitive way to look at this.

Consider set $X=\{1,2,\cdots,n\}$. Number of subsets of $X$ is $2^n$, depending on whether each element is included. Meanwhile if you consider subsets with exactly $k$ elements, this is $n \choose k$. Since $k=1,2,\cdots, n$, $$|\mathcal{P}(X)|=2^n=\sum_{k=1}^n {n\choose k}$$.

-