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\}$.
Best 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}$.