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 question already has an answer here:

I want to know if I can get some help with this proof. I tried, but I just cannot seem to get $2^{k}$. It states that,

For $k \in \mathbb{Z}_{\ge 0}$, $$\sum^{k}_{m=0}\binom{k}{m} = 2^k$$

Thank You.

share|improve this question
1  
Are you familiar with the binomial formula? Because once you know (or have proven) the binomial formula, what you want to prove should follow pretty quickly. –  Jesse Madnick Mar 17 '11 at 7:04
2  
How do you define the binomial coefficients? There are many (equivalent) ways and, depending on the way you choose, the proof you want is not the same. –  Did Mar 17 '11 at 7:31
    
@MarcvanLeeuwen Based on this meta discussion I think that this should be tagged (summation) and the tag (sequences-and-series) should not be used. (As far as I know, the later is intended for infinite sums. Although many questions about finite sums are tagged with this tag, since they were asked before (summation) tag was created.) –  Martin Sleziak Jan 9 at 8:59
    
About closing as a duplicate: One of the questions specifically asks for a proof about induction, the other does not have this restriction. –  Martin Sleziak Jan 9 at 9:00
add comment

marked as duplicate by Arthur Fischer Mar 30 at 11:37

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.

4 Answers

The right-hand side is the number of subsets of a set with $k$ elements. The left hand side gives a sum of the number of subsets of a set with $k$ elements having $0$ elements, then $1$ element, then $2$ elements, etc., up to the subsets with $k$ elements.

Leaving that aside, this follows from applying the binomial theorem in a way that might seem like a trick. Here's another example to motivate this. If $k\geq 1$, then $${k \choose 0}-{k \choose 1}+{k \choose 2}\mp\cdots +(-1)^k{k \choose k}=0.$$ Proof Sketch: Expand $(1-1)^k$ using the binomial theorem.

You could use induction and the factorial formula for the binomial coefficients, but I do not recommend doing so. However, using induction and Pascal's identity ${k\choose {m-1}}+{k\choose m}={{k+1}\choose m}$ would work well. Consider moving down a row in Pascal's triangle to motivate the proof. Each entry from row $k$ is added twice to obtain the entries in row $k+1$, so the sum of the entries doubles.

share|improve this answer
add comment

Take the binomial expansion of $(1+x)^k$.

\begin{equation} (1+x)^k = \sum_{m=0}^k \binom{k}{m} x^{k-m} \end{equation}

The above expansion holds for all values of $x$ and for all $k \geq 0$. Substitute $x=1$ and you have the result.

share|improve this answer
add comment

You can use induction.

$$\binom{k}{m}=\binom{k-1}{m-1}+\binom{k-1}{m}$$ is true for $k\in\mathbb{Z}_{>0}$ and $m\in\mathbb{Z}$.

Here: $$\binom{k}{m}:=0$$ if $m\notin\left\{ 0,\ldots,k\right\} $.

So: $$\sum_{m\in\mathbb{Z}}\binom{k}{m}=\sum_{m\in\mathbb{Z}}\binom{k-1}{m-1}+\sum_{m\in\mathbb{Z}}\binom{k-1}{m}=2^{k-1}+2^{k-1}=2^{k}$$

share|improve this answer
add comment

The LHS of the equation is counting the number of subsets of a set of $k$ elements. The RHS of the equation is a well-known formula for that.

share|improve this answer
add comment