About one generating function

Question

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.

Answer 1

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.)