12
$\begingroup$

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.

  • 0
    Are you trying to *prove* the identity using generating functions? Or do you want to compute the coefficients?2014-01-07

1 Answers 1

3

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.