Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to solve identity involving binomials and Fibonacci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose k}(-1)^{n-k}f_{2k+1}$$

My computational approach by Mathematica lead me to derive this generating function:


Can someone show how to transform both or any of the identity sides to obtain (coefficiens of) this generating function.

share|cite|improve this question
I suspect you need to use the shifted Legendre polynomials here $$P_{n}(2x-1) =(-1)^{n}\sum_{k=0}^n{n \choose k}{n+k\choose k}(-x)^{k}.$$ – Peter Bala Jul 26 '11 at 15:11
:I meant to add that their generating function (the shifted Legendre polynomials) is immediately obtainable from the generating function for the Legendre polynomials (see e.g. the relevant Wikipedia entry). The other ingredient you need will be Binet's formula for the Fibonacci numbers. – Peter Bala Jul 26 '11 at 15:24
Are you trying to prove the identity using generating functions? Or do you want to compute the coefficients? – ShreevatsaR Jan 7 '14 at 16:23

Here is a proof using complex variables. We seek to show that $$\sum_{k=0}^n {n\choose k} {n+k\choose k} F_{k+1} =\sum_{k=0}^n {n\choose k} {n+k\choose k} (-1)^{n-k} F_{2k+1}.$$

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

This yields the following expression for the sum on the LHS $$\frac{1}{2\pi i} \int_{|z|=1} \sum_{k=0}^n {n\choose k} \frac{1}{z^{k+1}} (1+z)^{n+k} \frac{\varphi^{k+1} - (-1/\varphi)^{k+1}}{\sqrt{5}} \; dz$$

This simplifies to $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|z|=1} \frac{(1+z)^n}{z} \sum_{k=0}^n {n\choose k} \left(\varphi\left(\varphi\frac{1+z}{z}\right)^k +\frac{1}{\varphi}\left(-\frac{1}{\varphi}\frac{1+z}{z}\right)^k \right)\; dz$$

This finally yields $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|z|=1} \frac{(1+z)^n}{z} \left( \varphi\left(1+\varphi\frac{1+z}{z}\right)^n +\frac{1}{\varphi}\left(1-\frac{1}{\varphi}\frac{1+z}{z}\right)^n \right) \; dz$$ or $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|z|=1} \frac{(1+z)^n}{z^{n+1}} \left( \varphi\left(z+\varphi(1+z)\right)^n +\frac{1}{\varphi}\left(z-\frac{1}{\varphi}(1+z)\right)^n \right) \; dz$$

Continuing we have the following expression for the sum on the RHS $$\frac{1}{2\pi i} \int_{|z|=1} \sum_{k=0}^n {n\choose k} (-1)^{n-k} \frac{1}{z^{k+1}} (1+z)^{n+k} \frac{\varphi^{2k+1} - (-1/\varphi)^{2k+1}}{\sqrt{5}} \; dz$$

This simplifies to $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|z|=1} \frac{(1+z)^n}{z} \\ \times \sum_{k=0}^n {n\choose k} (-1)^{n-k} \left(\varphi\left(\varphi^2\frac{1+z}{z}\right)^{k} +\frac{1}{\varphi}\left(\frac{1}{\varphi^2}\frac{1+z}{z}\right)^{k} \right)\; dz$$

This finally yields $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|z|=1} \frac{(1+z)^n}{z} \left( \varphi\left(-1+\varphi^2\frac{1+z}{z}\right)^n +\frac{1}{\varphi}\left(-1+\frac{1}{\varphi^2}\frac{1+z}{z}\right)^n \right) \; dz$$ or $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|z|=1} \frac{(1+z)^n}{z^{n+1}} \left( \varphi\left(-z+\varphi^2(1+z)\right)^n +\frac{1}{\varphi}\left(-z+\frac{1}{\varphi^2}(1+z)\right)^n \right) \; dz$$

Apply the substitution $z=1/w$ to this integral to obtain (the sign to correct the reverse orientation of the circle is canceled by the minus on the derivative) $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|w|=1} \left(1+\frac{1}{w}\right)^n w^{n+1} \\ \times \left( \varphi\left(-\frac{1}{w}+\varphi^2(1+\frac{1}{w})\right)^n +\frac{1}{\varphi} \left(-\frac{1}{w}+\frac{1}{\varphi^2}(1+\frac{1}{w})\right)^n \right) \frac{1}{w^2} \; dw$$ which is $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|w|=1} \left(1+\frac{1}{w}\right)^n \frac{1}{w} \\ \times \left( \varphi\left(-1+\varphi^2(w+1)\right)^n +\frac{1}{\varphi} \left(-1+\frac{1}{\varphi^2}(w+1)\right)^n \right) \; dw$$ which finally yields $$\frac{1}{\sqrt{5}}\frac{1}{2\pi i} \int_{|w|=1} \frac{(1+w)^n}{w^{n+1}} \\ \times \left( \varphi\left(-1+\varphi^2(w+1)\right)^n +\frac{1}{\varphi} \left(-1+\frac{1}{\varphi^2}(w+1)\right)^n \right) \; dw$$

This shows that the LHS is the same as the RHS because $$-1 + \varphi^2(w+1) = -1 + (1+\varphi)(w+1) = w + \varphi(w+1)$$ and $$-1+\frac{1}{\varphi^2}(w+1) = -1 + (1-\frac{1}{\varphi}) (w+1) \\ = -1 + (w+1) - \frac{1}{\varphi} (w+1) = w - \frac{1}{\varphi} (w+1).$$

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

share|cite|improve this answer

Your Answer


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.