$\sum_{k=0}^{n} \binom{n}{k}=2^{n} \overset{?}{\iff} \sum_{k=0}^{n} \binom{2n+1}{k}=2^{2n}$
Jack D'Aurizio narratively proved $\color{red}{\sum\limits_{k=0}^{n} \binom{2n+1}{k}=2^{2n}}$. Is this red equation related, and can it be transmogrified, to $\color{limegreen}{\sum\limits_{k=0}^{n} \binom{n}{k}=2^{n}}$?
I started my attempt by substituting $n = m/2$, because the RHS of the green target equation has the form $\color{limegreen}{2^?}$. Then $\color{red}{\sum\limits_{k=0}^{n} \binom{2n+1}{k}=2^{2n} \implies \sum\limits_{k=0}^{m/2} \binom{m+1}{k}=2^{m}}$. But now what do I do? I can't rewrite $m$, again because the RHS of the target equation has the form $\color{limegreen}{2^?}$.
- Give a story proof that $\sum\limits_{k=0}^{n} \binom{n}{k}=2^{n}$.
Blitzstein. Introduction to Probability (2019 2 ed). p 35.
1 answer
The green result can be used to prove the red one, yes.
Start with the fact that $\binom{m}{k} = \binom{m}{m - k}$. If this isn't obvious to you, you can derive it either by looking at the usual formula for the binomial, or by considering that choosing the members of a subset is equivalent to choosing elements excluded from the subset.
You can use that fact to see that $\sum_{k=0}^n \binom{2n + 1}{k} = \sum_{k=0}^n \binom{2n + 1}{2n + 1 - k}$. Considering the set of numbers $\{2n + 1 - k \mid k \in \{ 0,\dots,n \}\}$, you can see that this set is the same as $\{n + 1,\dots, 2n + 1\}$, so another way to write $\sum_{k=0}^n \binom{2n + 1}{2n + 1 - k}$ is $\sum_{k=n + 1}^{2n + 1} \binom{2n + 1}{k}$.
Then, of course, $\sum_{k=0}^n \binom{2n + 1}{k} + \sum_{k=n + 1}^{2n + 1} \binom{2n + 1}{k} = \sum_{k=0}^{2n + 1} \binom{2n + 1}{k}$, which by the green equation is equal to $2^{2n + 1}$. But from the previous paragraph, we know the summands on the left are equal to each other, so they must each be equal to half of the result, or $2^{2n}$. This proves the red equation. (You need a little more to go the other way; using this line of reasoning starting with the red equation would only prove that the green equation holds for odd $n$.)
2 comment threads