Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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