Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be $(-1)^ng_{n+1}(-4)$. I tried to factorize ${n + k \choose 2k}$ to ${n+k \choose k}{n \choose k}/{2k \choose k}$. It is known that $$(1-x)^{-n-1} = \sum_{k=0}^{\infty}{n + k \choose k}x^k,$$ $$(1-4x)^{-1/2} = \sum_{k=0}^{\infty}{2k \choose k}x^k,$$ $$(1+x)^n = \sum_{k=0}^n{n \choose k}x^k.$$ I have tried to combine these formulae, but nothing interesting has been found yet.

-
Have you tried out some small values of $n$ to see if there's a pattern? – Thomas Andrews Dec 27 '11 at 20:47
(It looked to me like there was an obvious pattern starting with $n=0,1,2$.) – Thomas Andrews Dec 27 '11 at 20:52

Your sum can be rewritten like so: \begin{align} \sum_{k=0}^{n+1} (-1)^{n-k} 4^k \binom{n+k+1}{2k} &= \sum_{k=0}^{n+1} (-1)^{n-k} 4^k \binom{n+1+k}{n+1-k} \\ &= \sum_{j \geq 0} (-1)^{j-1} 4^{n+1-j} \binom{2(n+1)-j}{j} \\ &= \sum_{j \geq 0} (-1)^{j-1} 4^{m/2-j} \binom{m-j}{j} \\ &= - \frac{1}{2^m}\sum_{j \geq 0} (-1)^j 4^{m-j} \binom{m-j}{j}, \\ \end{align} where we switched indices twice via $k = n+1-j$ and $m = 2n+2$. So what we need is the bivariate generating function of the sum $$G_m(x,y) = \sum_{j \geq 0} \binom{m-j}{j} x^j y^{m-j}.$$ (Note that when $x = y= 1$ this gives $F_{m+1}$, the $m+1$ Fibonacci number.)

I considered this generating function in this answer. In particular, $G(x,y)$ satisfies the recurrence $$G_m(x,y) = y G_{m-1}(x,y) + xy G_{m-2}(x,y)$$ with initial conditions $G_0(x,y) = 1$, $G_1(x,y) = y$. With $x = -1, y = 4$, we need to solve $$G_m = 4 G_{m-1} -4 G_{m-2},$$ which has auxiliary equation $z^2 - 4z + 4 = 0$. There is a double root at $z = 2$, and so the general solution is $G_m = A2^m + Bm 2^m$. Subbing in the initial conditions, we have $$G_m = 2^m + m 2^m.$$ Therefore, $$\frac{-1}{2^m} \sum_{j \geq 0} (-1)^j 4^{m-j} \binom{m-j}{j} = \frac{-1}{2^m} (2^m + m 2^m) = -1 -m.$$ Since $m = 2n+2$, subbing back in terms of $n$ gives us the answer you're after: $$\sum_{k=0}^{n+1} (-1)^{n-k} 4^k \binom{n+k+1}{2k} = -1 -(2n+2) = -2n-3.$$

More generally, the bivariate generating function is $$G_m(x,y) = \frac{\left(y + \sqrt{y^2+4xy}\right)^{m+1} - \left(y - \sqrt{y^2+4xy}\right)^{m+1}}{2^{m+1}\sqrt{y^2+4xy}},$$ provided, of course, that $y^2 + 4xy \neq 0$. However, this is precisely the case that the OP's question falls in, and so we have to go to the recurrence relation to find the solution. (Binet's formula for the Fibonacci numbers is obtained by setting $x = y = 1$, so this is a generalization of that formula.)

-

Suppose we seek to evaluate $$\sum_{k=0}^{n+1} {n+1+k\choose 2k} (-1)^{n-k} 4^k = (-1)^n \sum_{k=0}^{n+1} {n+1+k\choose n+1-k} (-4)^k.$$

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

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

Observe that the defining integral of the binomial coefficient is zero when $n+2 -k < 1.$ This condition is precisely $n-k < -1$ or $k > n+1.$ Therefore we may extend the sum to infinity.

We thus have $$\frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{z^{n+2}} \sum_{k=0}^\infty (1+z)^k \times z^k \times (-4)^k\; dz \\ = \frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{z^{n+2}} \frac{1}{1+4(1+z)z} \; dz. \\ = \frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{z^{n+2}} \frac{1}{(1+2z)^2} \; dz.$$

Therefore the value of the integral is given by $$(-1)^n [z^{n+1}] \frac{(1+z)^{n+1}}{(1+2z)^2} = (-1)^n \sum_{q=0}^{n+1} {n+1\choose n+1-q} (q+1) (-2)^q \\= (-1)^n \sum_{q=0}^{n+1} {n+1\choose q} (q+1) (-2)^q.$$

Recall that $$(z (1+z)^n)' = \sum_{q=0}^n {n \choose q} (q+1) z^q = (1+z)^n + nz(1+z)^{n-1}$$ so that the end result for the sum is $$(-1)^n \times ((-1)^{n+1} - 2(n+1)(-1)^n) = -1 - 2(n+1) = -3 - 2n.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

The reader is invited to try this method on the binomial coefficient $${n+1+k\choose 2k}$$ and examine carefully what happens.

-