20
$\begingroup$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a series of algebraic manipulations that can lead from $\sum\limits_{i=0}^n \binom{n}{i}$ to $2^n$.

$\endgroup$
  • 11
    $\begingroup$ is the proof you looking for using $(1+1)^n=2^n$? $\endgroup$ – Arjang Jan 24 '11 at 4:30
  • $\begingroup$ Well, no. That one I was also aware of. It's more of a curiosity if there's any direct method to go from the summation to $2^n$. $\endgroup$ – JSchlather Jan 24 '11 at 4:40
  • 5
    $\begingroup$ One should not think of the algebraic and combinatorial proofs as different. There is a straightforward dictionary between algebra and combinatorics in these cases (and it is given by taking generating functions). $\endgroup$ – Qiaochu Yuan Jan 24 '11 at 9:12
  • $\begingroup$ Zeilberger's algorithm might do it - it's a useful tool for this kind of problem in general (sum from $-\infty$ to $\infty$ of a hypergeometric with finite support). $\endgroup$ – Peter Taylor Jan 24 '11 at 9:29
  • 1
    $\begingroup$ @PeterTamaroff It was a sort of silly question that I asked over a year ago because I had always thought of binomial coefficients being defined as $n!/(k!(n-k)!)$ and was always curious how one could go from this sum of factorials divided by other factorials to $2^n$. When I had said direct, I had meant something along the lines of proving the binomial recurrence by moving factorials around. It's not a very clear question in retrospect. But people seemed to get the basic idea of what I wanted. $\endgroup$ – JSchlather Apr 27 '12 at 19:23
20
$\begingroup$

Here's one. Let $g(n) = \sum \limits_{i=0}^n \binom{n}{i}$. Then

$$g(n+1) - g(n) = \sum_{i=0}^{n+1} \binom{n+1}{i} - \sum_{i=0}^n \binom{n}{i} = \sum_{i=0}^{n+1} \left(\binom{n+1}{i} - \binom{n}{i}\right) = \sum_{i=0}^{n+1} \binom{n}{i-1} $$ $$= \sum_{i=0}^n \binom{n}{i} = g(n).$$ Here, we use the fact that $\binom{n}{n+1} = \binom{n}{-1} = 0$, as well as the binomial recurrence $\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$.

Thus we have $g(n+1) = 2g(n)$, with $g(0) = 1$. Since $g(n)$ doubles each time $n$ is incremented by 1, we must have $$g(n) = \sum_{i=0}^n \binom{n}{i} = 2^n.$$

$\endgroup$
  • 4
    $\begingroup$ This is more or less the same proof one would do to show that $(a+b)^n$ is what it is... $\endgroup$ – Mariano Suárez-Álvarez Jan 24 '11 at 5:40
  • $\begingroup$ @Mariano: Good observation. In fact, see the proof of Identity 1 in this paper: math.pugetsound.edu/~mspivey/CombSum.pdf $\endgroup$ – Mike Spivey Jan 24 '11 at 5:57
  • 1
    $\begingroup$ Very nice and this proof seems to be analogous to what picakhu did as well. $\endgroup$ – JSchlather Jan 24 '11 at 5:57
15
$\begingroup$

Simply use the binomial formula.

$$(a + b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n - k}$$

With $a = b = 1$ you have your result.

$\endgroup$
11
$\begingroup$

Well, here is one.

$$\sum_{i=0}^n \binom{n}{i}=2^n$$ $$\sum_{i=0}^n \binom{n}{i}+\sum_{i=0}^n \binom{n}{i}=2^{n+1}$$ $$\binom{n}{0}+\left [ \binom{n}{0}+\binom{n}{1} \right ]+...+\left [ \binom{n}{n-1}+\binom{n}{n}\right ]+\binom{n}{n}=2^{n+1}$$ $$\sum_{i=0}^{n+1} \binom{n+1}{i}=2^{n+1}$$

$\endgroup$
  • $\begingroup$ So you're using induction? And I assume that in your last step it should be $\sum_{i=0}^{n+1}\binom{n+1}{i}$? $\endgroup$ – JSchlather Jan 24 '11 at 4:41
  • $\begingroup$ Yup, sorry about that. $\endgroup$ – picakhu Jan 24 '11 at 4:43
  • $\begingroup$ $\sum_{i=0}^0 \binom{0}{i} = 2^n$ $\endgroup$ – zapyourtumor Mar 24 '18 at 3:02
3
$\begingroup$

You could use exponential generating functions to prove this identity. $$\begin{eqnarray}\sum_{n\ge0}2^n\frac{x^n}{n!}&=&\sum_{n\ge0}\frac{(2x)^n}{n!}\\&=&e^{2x}\\&=&e^xe^x\\&=&\sum_{i\ge0}\frac{x^i}{i!}\sum_{j\ge0}\frac{x^j}{j!}\\&=&\sum_{n\ge0}\sum_{i=0}^{n}\frac{x^i}{i!}\frac{x^{n-i}}{(n-i)!}\\&=&\sum_{n\ge0}\sum_{i=0}^n\binom{n}{i}\frac{x^n}{n!}\end{eqnarray} $$ Now, comparing the coefficients of $x^n$ for ${n\ge0}$ gives the identity.

$\endgroup$
2
$\begingroup$

Using the binomial theorem, we find:

$2^n = (1 + 1)^n = \sum\limits_{k=0}^{n} \binom{n}{k} 1^k*1^{n-k} = \sum\limits_{k=0}^{n} \binom{n}{k}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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