1. ## Sumatory

Calculate:$\displaystyle \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:$\displaystyle \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 $\displaystyle 2n-k\choose n$ is the coefficient of $\displaystyle x^n$ in $\displaystyle (1+x)^{2n-k}$.

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

But (writing the terms in reverse order) $\displaystyle 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 $\displaystyle \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 $\displaystyle x^n$ in that expression is the sum of all the binomial coefficients of powers of x in $\displaystyle 2^{n+1}(1+x)^n$ minus the sum of the coefficients in the first half of the expansion of $\displaystyle (1+x)^{2n+1}$.

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

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

3. wonderfull