Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

marked as duplicate by Marc van Leeuwen, Gigili, mau, Michael Albanese, Elias Jan 9 at 10:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
1  
@HassanMuhammad $2^{k+1}=2 \times 2^k=2^k+2^k$ –  Mark Bennet Aug 1 '12 at 5:43
add comment

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

share|improve this answer
    
Thanks for your help –  Jason Curt Aug 1 '12 at 2:58
add comment

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

Substituting $x=1$ gives the desired conclusion.

share|improve this answer
    
This is one of the easiest proofs, but OP was asking for an inductive route... –  J. M. Aug 1 '12 at 2:14
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.