# Generating function of even Fibonacci numbers

I am trying to prove the Fibonacci number identity $$\sum_{k = 0}^n {n \choose k} F_k = F_{2n}$$ with generating functions.

If we let $$G(x) = \sum_{k \geq 0} \frac{F_k}{k!} x^k$$ be the exponential generating function of the Fibonacci numbers, the left hand side has the exponential generating function $$G(x) e^x$$. If we could express the right-hand side in terms of $$G$$ then we could just check that the two are equal. However, I can't seem to figure out the right-hand side.

How can I find the exponential generating function of the sequence $$\{F_{2n}\}$$ without using Binet's formula? (With Binet's formula it is pretty straightforward, but so is the original identity.)

To be clear, the generating function $$\frac{G(x) + G(-x)}{2}$$ does not work. It generates the sequence $$\{F_0, 0, F_2, 0, F_4, \cdots\}$$, which is not right. I want to generate $$\{F_0, F_2, F_4, \cdots\}$$.

• Since the OGF and EGF for Fibonacci numbers are essentially equivalent to Binet's formula, you are essentially asking to prove Binet's formula. What would be the point of that? – Somos Apr 4 at 1:32
• @Somos You're right that this is the case for the Fibonacci numbers (and any sequence satisfying a recurrence with constant coefficients). I was hoping that a general trick would exist without reference to Binet, so that it would work for more complicated sequences. – rwbogl Apr 4 at 1:39
• In that case, ask that question instead, but I doubt that you could do it for EGF, while OGF case is simple as you probably already know using multi-section of generating function power series.. – Somos Apr 4 at 1:42

## 1 Answer

I do not think EGF's are the way to go here. There is just no nice way to extract the EGF for $$F_{2n}$$ from that of $$F_n$$. But here is an OGF solution.

First, calculate the OGF of the left hand side. \begin{align} \sum_{n\ge 0}x^n\sum_{k=0}^n \binom{n}kF_k &=\sum_{k\ge 0}F_k\sum_{n\ge k} \binom{n}kx^n \\&=\sum_{k\ge 0}F_k\sum_{n\ge k} (-1)^{n-k}\binom{-k-1}{n-k}x^n \\&=\sum_{k\ge 0}F_kx^k\sum_{n\ge k} \binom{-k-1}{n-k}(-x)^{n-k} \\&=\sum_{k\ge 0}F_kx^k\sum_{n\ge 0} \binom{-k-1}{n}(-x)^{n} \\&=\sum_{k\ge 0}F_kx^k(1-x)^{-k-1} \\&=(1-x)^{-1}\sum_{k\ge 0}F_k\times \left(\frac{x}{1-x}\right)^k \end{align} Now, recalling that the generating function for the Fibonacci numbers is $$f(z):=\sum_{k\ge 0} F_kz^k=\frac{z}{1-z-z^2}$$, this is equal to $$\sum_{n\ge 0}x^n\left(\sum_{k=0}^n \binom{n}kF_k\right)=(1-x)^{-1}\cdot \frac{\left(\frac{x}{1-x}\right)}{1-\left(\frac{x}{1-x}\right)-\left(\frac{x}{1-x}\right)^2}.$$ You can then verify this is the same thing as $$\frac{F(\sqrt{x})+F(-\sqrt{x})}2$$, the OGF for $$F_{2n}$$.