# Evaluating Combination Sum $\sum{n+k\choose 2k} 2^{n-k}$

Evaluate $$\sum_{k=0}^n{n+k\choose 2k} 2^{n-k}$$ So im not really sure how to begin with this. I would imagine we start with dividing out $2^{n}$, but not really sure much past that

The method used here is that of the generating function. Let $S_{n}$ be the series to be summed \begin{align} S_{n} = \sum_{k=0}^{n} \binom{n+k}{2k} \ 2^{n-k}. \end{align} The generating function and its reduction are as follows. \begin{align} \sum_{n=0}^{\infty} S_{n} \frac{t^{n}}{2^{n}} &= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{n+k}{2k} \ 2^{n-k} \ \frac{t^{n}}{2^{n}} \\ &= \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \binom{n+2k}{2k} \ 2^{-k} t^{n+k} \\ &= \sum_{k=0}^{\infty} \frac{t^{k}}{2^{k}} \cdot \sum_{n=0}^{\infty} \frac{(2k+1)_{n} t^{n}}{n!} \\ &= \sum_{k=0}^{\infty} \frac{t^{k}}{2^{k}} \cdot (1-t)^{-2k-1} \\ &= \frac{1}{1-t} \sum_{k=0}^{\infty} \left( \frac{t}{2(1-t)^{2}} \right)^{k} = \frac{1-t}{1 - (5/2)t + t^{2}}. \end{align}

Now, \begin{align} \frac{1-t}{1 - (5/2)t + t^{2}} &= \frac{1-t}{(1/2-t)(2-t)} = \frac{2}{3} \left[ \frac{1}{1-2t} + \frac{1}{2(1-t/2)} \right] \\ &= \sum_{n=0}^{\infty} \left[ \frac{2^{2n+1}+1}{3 \cdot 2^{n}} \right] \ t^{n} \end{align}
and \begin{align} \sum_{n=0}^{\infty} S_{n} \frac{t^{n}}{2^{n}} = \sum_{n=0}^{\infty} \left[ \frac{2^{2n+1}+1}{3 \cdot 2^{n}} \right] \ t^{n} \end{align} which yields \begin{align} \sum_{k=0}^{n} \binom{n+k}{2k} \ 2^{n-k} = \frac{2^{2n+1}+1}{3}. \end{align}

• brilliant, thanks a bunch – Mr.Meeseeks May 13 '14 at 5:57
• @MarkoRiedel Yes. I just up vote your answer. Thanks. – Felix Marin Aug 13 '14 at 0:41
• Can you please explain second step in reduction generating function: how do you get from sum to $n$ to sum to $\infty$? – Evgenii Egorov Sep 26 '16 at 8:47

Suppose we seek to evaluate $$\sum_{k=0}^n {n+k\choose 2k} 2^{n-k}$$ inspired by the work at this MSE link I and this MSE link II.

Start from $${n+k\choose 2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2k+1}} (1+z)^{n+k} dz.$$

This yields the following expression for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k=0}^n \frac{1}{z^{2k+1}} (1+z)^{n+k} \times 2^{n-k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} 2^n \times \frac{(1+z)^n}{z} \sum_{k=0}^n \left(\frac{1+z}{2z^2}\right)^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} 2^n \times \frac{(1+z)^n}{z} \frac{\left(\frac{1+z}{2z^2}\right)^{n+1} - 1} {\frac{1+z}{2z^2} - 1} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} 2^n \times \frac{(1+z)^n}{z \times (2z^2)^{n+1}} \frac{(1+z)^{n+1} - (2z^2)^{n+1}} {\frac{1+z}{2z^2} - 1} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} 2^n \times \frac{(1+z)^n}{z \times (2z^2)^n} \frac{(1+z)^{n+1} - (2z^2)^{n+1}} {1+z - 2z^2} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{2n+1}} \frac{(1+z)^{n+1} - (2z^2)^{n+1}} {1+z - 2z^2} \; dz.$$

It now follows from the Cauchy Residue Theorem that the integral is given by $$[z^{2n}] \left((1+z)^n \times \frac{(1+z)^{n+1} - (2z^2)^{n+1}} {1+z - 2z^2}\right).$$

The term in $(2z^2)^{n+1}$ starts at $z^{2n+2}$ and hence does not contribute. This leaves $$[z^{2n}] \frac{(1+z)^{2n+1}}{1+z - 2z^2} = [z^{2n}] (1+z)^{2n+1} \left(\frac{2}{3}\frac{1}{1+2z} +\frac{1}{3}\frac{1}{1-z}\right).$$

This finally yields for the coefficient the value $$\sum_{q=0}^{2n} \left( [z^{2n-q}] \frac{1}{1+z - 2z^2} \right) {2n+1\choose q} \\ = \sum_{q=0}^{2n} {2n+1\choose q} \frac{2}{3} (-2)^{2n-q} + \sum_{q=0}^{2n} {2n+1\choose q} \frac{1}{3} \times 1^{2n-q} \\= +\frac{1}{3} + \frac{2}{3} \sum_{q=0}^{2n+1} {2n+1\choose q} (-2)^{2n-q} + \frac{1}{3} (2^{2n+1} - 1) \\= +\frac{1}{3} + \frac{2}{3} \times 2^{2n} \times \sum_{q=0}^{2n+1} {2n+1\choose q} (-2)^{-q} + \frac{1}{3} (2^{2n+1} - 1) \\ = +\frac{1}{3} + \frac{2}{3} \times 2^{2n} \times \left(1 - \frac{1}{2}\right)^{2n+1} + \frac{1}{3} (2^{2n+1} - 1) \\ = +\frac{1}{3} + \frac{1}{3} + \frac{1}{3} (2^{2n+1} - 1).$$ This is $$\frac{2^{2n+1}+1}{3}.$$

Quite a remarkable method and suitable for implementation by a CAS. (The algebra is very simple even if it may appear challenging at first sight.)

• +1. I just found your comment in another page. Thanks. – Felix Marin Aug 13 '14 at 0:40
• Thanks. I linked to two of your posts where you present this method at the beginning of the above answer. – Marko Riedel Aug 13 '14 at 0:44
• I just check them. Thanks. – Felix Marin Aug 13 '14 at 0:45

Let's rewrite our sum $S(2n)$ as $\sum_l\binom{2n-l}l2^l$.

Recall that $\binom{2n-l}l$ is the number of tilings of a rectangle $1\times 2n$ by $l$ dominoes and $2n-2l$ squares (we choose which of $2n-l$ tiles are dominoes). So $S(2n)$ counts the number of tiling of a rectangle $1\times 2n$ by squares and two kinds of dominoes.

So obviously $S(N)=S(N-1)+2S(N-2)$ (cf. Fibonacci numbers). This linear recurrence can be solved using standard methods.