# Construction of generating function from identity

I am trying to solve identity involving binomials and fibbonaci 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