Tuesday 7 January 2020

summation - Prove the identity $binom{2n+1}{0} + binom{2n+1}{1} + cdots + binom{2n+1}{n} = 4^n$



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}$


Answer



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.



No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...