I've worked out a proof, but I was wondering about alternate, possibly more elegant ways to prove the statement. This is my (hopefully correct) proof:

Starting from the identity $2^m = \sum_{k=0}^m \binom{m}{k}$ (easily derived from the binomial theorem), with $m = 2n$:

$2^{2n} = 4^n = \binom{2n}{0} + \binom{2n}{1} + \cdots + \binom{2n}{2n-1} + \binom{2n}{2n}$

Applying the property $\binom{m}{k} = \binom{m}{m-k}$ to the second half of the list of summands in RHS above:

$4^n = \binom{2n}{0} + \binom{2n}{1} + \cdots + \binom{2n}{n-1} + \binom{2n}{n} + \underbrace{\binom{2n}{n-1} +\cdots \binom{2n}{1} + \binom{2n}{0}}_{\binom{m}{k} = \binom{m}{m-k} \text{ has been applied}}$

Rearranging the above sum by alternately taking terms from the front and end of the summand list in RHS above (and introducing the term $\binom{2n}{-1} = 0$ at the beginning just to make explicit the pattern being developed):

$4^n = (\binom{2n}{-1} + \binom{2n}{0}) + (\binom{2n}{0} + \binom{2n}{1}) + \cdots + (\binom{2n}{n-1} + \binom{2n}{n})$

Finally, using the property $\binom{m}{k} + \binom{m}{k-1} = \binom{m+1}{k}$ on the paired summands, we get the desired result:

$4^n = \binom{2n+1}{0} + \binom{2n+1}{1} + \cdots + \binom{2n+1}{n}$


Why not just $$ \begin{align} 2^{2n+1} &=\binom{2n+1}{0}+\cdots+\binom{2n+1}{n}+\binom{2n+1}{n+1}+\cdots+\binom{2n+1}{2n+1} \\ &=\binom{2n+1}{0}+\cdots+\binom{2n+1}{n}+\binom{2n+1}{n}+\cdots+\binom{2n+1}{0} \\ &=2\left[\binom{2n+1}{0}+\cdots+\binom{2n+1}{n}\right] \end{align} $$ Then divide each extremity by 2.


Applying what you mention on (in this context nicer) odd $2n+1$ instead of even $2n$ we find:$$2\times4^n=2^{2n+1}=\sum_{k=0}^{2n+1}\binom{2n+1}{k}=2\sum_{k=0}^{n}\binom{2n+1}{k}$$

Now divide by $2$.

  • 2
    $\begingroup$ Side question: if by "$2.4$" you mean "$2\cdot4$", then what decimal representation do you use for $2+\frac{4}{10}$? $\endgroup$ – barak manos Jan 11 '16 at 11:24
  • $\begingroup$ @barak In the Netherlands we write $2,4$. That's my (invalid) excuse for overlooking it. $\endgroup$ – drhab Jan 11 '16 at 12:22

Let $A$ be the powerset (i.e., the set of subsets of) of $\{1,\ldots,2n\}$. Let $B$ the set of all subsets of $\{1,\ldots,2n+1\}$ at most $n$ elements. Then "clearly" $|A|=2^{2n}=4^n$ and $|B|=\sum_{k=0}^n{2n+1\choose k}$. Define the following map $f\colon B\to A$: $$f(S)=\begin{cases}S&\text{if }2n+1\notin S\\\{1,\ldots,2n+1\}\setminus S&\text{if }2n+1\in S\end{cases} $$ and define $g\colon A\to B$ by $$g(S)=\begin{cases}S&\text{if }|S|\le n\\\{1,\ldots,2n+1\}\setminus S&\text{if }|S|>n\end{cases} $$ Finally, verify that $f$ and $g$ are inverse of each other, hence $|A|=|B|$.


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.