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.

Solution 1:

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}$$

Solution 2:

Marvis's hint suffices. Anyways:

Base case at $n = 0$ is trivial to show: $2^0 = 1 = \dbinom{0}{0} = 1.$
Inductive hypothesis: assume $$ 2^k = \binom{k}{0} + \binom{k}{1} + \ldots + \binom{k}{k} \tag{1} $$
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 $$

Solution 3:

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

Substituting $x=1$ gives the desired conclusion.

Solution 4:

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.