<s>[INST] Help with a combinatoric formula Anyone can help solve th following? $\left( {\begin{array}{*{20}{c}}
  {2n} \\ 
  n 
\end{array}} \right)$  means $2n$ chooses $n$. Thanks!
$\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}}
  {2k} \\ 
  k 
\end{array}} \right){2^{ - 2k}}}  = \sum\limits_{k = 0}^n {\frac{{(2k)!}}{{k!k!}}{2^{ - 2k}}}  = \frac{{(2n)!}}{{n!n!}}(2n + 1){2^{ - 2n}} = \left( {\begin{array}{*{20}{c}}
  {2n} \\ 
  n 
\end{array}} \right){2^{ - 2n}}(2n + 1)$
The report from wolframalpha shows they indeed equal.

 [/INST] How about induction? The base case $n = 0$ is easily verified. Then
\begin{align}
\binom{2n}{n}2^{-2n}(2n+1) + \binom{2n+2}{n+1}2^{-2n-2} &= \binom{2n+2}{n+1}2^{-2n-2}\biggl[\frac{4(n+1)^2}{2n+2} + 1\biggr] \\
&= \binom{2n+2}{n+1}2^{-2n-2}\bigl(2n+2+1\bigr)
\end{align}
is the induction step.
</s>