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$.
$\begingroup$
$\endgroup$
9
-
11$\begingroup$ is the proof you looking for using $(1+1)^n=2^n$? $\endgroup$– jimjimCommented Jan 24, 2011 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$– JSchlatherCommented Jan 24, 2011 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 YuanCommented Jan 24, 2011 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 TaylorCommented Jan 24, 2011 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$– JSchlatherCommented Apr 27, 2012 at 19:23
|
Show 4 more comments
5 Answers
$\begingroup$
$\endgroup$
4
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.$$
answered Jan 24, 2011 at 5:37
-
4$\begingroup$ This is more or less the same proof one would do to show that $(a+b)^n$ is what it is... $\endgroup$ Commented Jan 24, 2011 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$ Commented Jan 24, 2011 at 5:57
-
1$\begingroup$ Very nice and this proof seems to be analogous to what picakhu did as well. $\endgroup$ Commented Jan 24, 2011 at 5:57
-
$\begingroup$ @Mike Spivey, Respected Mr Spivey, $\sum_{i=0}^{n+1} \binom{n+1}{i}$ is the sum of binoms $\binom{n+1}{i}$ in the range from $0$ to $(n+1)$, $\sum_{i=0}^n \binom{n}{i}$ is the sum of binoms $\binom{n}{i}$ in the range from $0$ to $n$, but how can you insert the term $\binom{n}{i}$ into the sum $\sum_{i=0}^{n+1} \left( \binom{n+1}{i}-\binom{n}{i} \right)$, if that term $\binom{n}{i}$ has the another range? Explain, please. $\endgroup$ Commented Apr 17 at 13:54
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
3
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}$$
-
$\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$ Commented Jan 24, 2011 at 4:41
-
-
$\begingroup$ $\sum_{i=0}^0 \binom{0}{i} = 2^n$ $\endgroup$ Commented Mar 24, 2018 at 3:02
$\begingroup$
$\endgroup$
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.
answered Mar 5, 2014 at 12:42
$\begingroup$
$\endgroup$
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}$