# Construction of generating function from identity

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:

$$\frac{\sqrt{3x^2-2x+3+2\sqrt{x^4-8x^3-2x^2-8x+1}}}{\sqrt{5}\sqrt{x^4-8x^3-2x^2-8x+1}}$$

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

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

-