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}

  • $\begingroup$ brilliant, thanks a bunch $\endgroup$ – Mr.Meeseeks May 13 '14 at 5:57
  • $\begingroup$ @MarkoRiedel Yes. I just up vote your answer. Thanks. $\endgroup$ – Felix Marin Aug 13 '14 at 0:41
  • $\begingroup$ Can you please explain second step in reduction generating function: how do you get from sum to $n$ to sum to $\infty$? $\endgroup$ – Evgeny 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.)

  • $\begingroup$ +1. I just found your comment in another page. Thanks. $\endgroup$ – Felix Marin Aug 13 '14 at 0:40
  • $\begingroup$ Thanks. I linked to two of your posts where you present this method at the beginning of the above answer. $\endgroup$ – Marko Riedel Aug 13 '14 at 0:44
  • $\begingroup$ I just check them. Thanks. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.