1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Somos Apr 4 at 1:32
  • $\begingroup$ @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. $\endgroup$ – rwbogl Apr 4 at 1:39
  • 1
    $\begingroup$ 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.. $\endgroup$ – Somos Apr 4 at 1:42
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.