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
Solution 1:
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}
Solution 2:
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.)