0
$\begingroup$

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.

  • 0
    So, what have you tried? What definition of the binomial coefficients are you using?2012-08-01
  • 0
    Well I've tried this: 2^(k+1) = C(k+1, 0) + C(K+1, 1) ... C(K+1, K+1)2012-08-01
  • 0
    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)?2012-08-01
  • 0
    You haven't answered my second question. What definition of the binomial coefficients are you using? Factorials? Recursion relation? Something else?2012-08-01
  • 0
    To be honest I'm not quite sure since binomial coefficients weren't mentioned in the course2012-08-01

5 Answers 5

1

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

6

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

4

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

  • 0
    BTW $\dbinom{x}{y} = C(x, y).$2012-08-01
  • 0
    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...2012-08-01
  • 0
    @J.D.: Please can you explain why $2^{k+1}=2^{k}+2^{k}$?2012-08-01
  • 1
    @HassanMuhammad $2^{k+1}=2 \times 2^k=2^k+2^k$2012-08-01
2

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

Substituting $x=1$ gives the desired conclusion.

  • 0
    This is one of the easiest proofs, but OP was asking for an inductive route...2012-08-01
2

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.