# Math Help - Sumatory

1. ## Sumatory

Calculate: $
\sum\limits_{k = 0}^n {2^k } \left( {\begin{array}{*{20}c}
{2n - k} \\
n \\

\end{array} } \right)
$

Thanks

2. Originally Posted by Nacho
Calculate: $
\sum\limits_{k = 0}^n {2^k } \left( {\begin{array}{*{20}c}
{2n - k} \\
n \\

\end{array} } \right)
$
This seems quite hard. Start by noticing that $2n-k\choose n$ is the coefficient of $x^n$ in $(1+x)^{2n-k}$.

Therefore $\sum_{k=0}^n 2^k{2n-k\choose n}$ is the coefficient of $x^n$ in $\sum_{k=0}^n 2^k(1+x)^{2n-k} = f(x)$.

But (writing the terms in reverse order) $f(x) = 2^n(1+x)^n\sum_{k=0}^n\bigl(\tfrac12(1+x)\bigr)^k = 2^n(1+x)^n \frac{1-\bigl(\tfrac12(1+x)\bigr)^{n+1}}{1-\tfrac12(1+x)}$ (sum of geometric series), and this simplifies to $\frac{2^{n+1}(1+x)^n - (1+x)^{2n+1}}{1-x} = \bigl(2^{n+1}(1+x)^n - (1+x)^{2n+1}\bigr)(1+x+x^2+\ldots)$. The coefficient of $x^n$ in that expression is the sum of all the binomial coefficients of powers of x in $2^{n+1}(1+x)^n$ minus the sum of the coefficients in the first half of the expansion of $(1+x)^{2n+1}$.

But the sum $\sum_{k=0}^n {n\choose k}$ of all the binomial coefficients of powers of x in $(1+x)^n$ is $2^n$. Also, the symmetry of the binomial coefficients (the fact that $\textstyle{n\choose k} = {n\choose n-k}$) means that the sum $\sum_{k=0}^n{2n+1\choose k}$ of the coefficients in the first half of the expansion of $(1+x)^{2n+1}$ is $\tfrac122^{2n+1} = 2^{2n}$.

Therefore $\sum_{k=0}^n 2^k{2n-k\choose n} = 2^{n+1}\!\!\times2^n-2^{2n} = 4^n$.

3. wonderfull