Generating Functions with Fibonacci

Question

a) Let \begin{align*} F_{\text{even}}(x) &= F_0x^0 + F_2x^2 + F_4x^4 + F_6x^6 + F_8x^8 + \cdots \\ &= x^2 + 3x^4 + 8x^6 + 21x^8 + \cdots \end{align*} be the generating function whose coefficient of $x^n$ is the $n^{\text{th}}$ Fibonacci number for even $n$, and is zero for odd $n$.

Write $F_{\text{even}}(x)$ as a rational function (that is, as a simplified quotient of polynomials).

b) For what ordered pair of constants $(a,b)$ is it true that $F_{2n}=aF_{2n-2}+bF_{2n-4}$ for all integers $n\ge 2$?

---

How can I approach this with generating functions?

Answer 1

Repeating Slade's hint, for every generating function $F$, it is the case that $$F_{\mathrm{even}}(x) = \frac{F(x) + F(-x)}{2}. $$ Similarly, we have $$F_{\mathrm{odd}}(x) = \frac{F(x) - F(-x)}{2}. $$ Even more generally, for any $k$ and $m$ we can consider $$ F_{m,k} = \frac{1}{m} \sum_{t=0}^m \omega^{kt} F(\omega^{-t} x), $$ where $\omega$ is a primitive $m$th root of unity. The coefficient of $x^n$ in $F_{m,k}$ is $$ F_n \frac{1}{m} \sum_{t=0}^m \omega^{(k-n)t}. $$ When $n \equiv k \pmod{m}$, the sum equals $1$, and otherwise it vanishes. So $F_{m,k}$ contains those powers $n$ such that $n \equiv k \pmod{m}$.

As Lucian comments, for your particular case you get $$ F_{\mathrm{even}}(x) = \frac{x^2}{x^4 - 3x^2 + 1}, $$ which implies that $$ (x^4 - 3x^2 + 1) F_{\mathrm{even}}(x) = x^2. $$ You should be able to deduce $a,b$ from this.

Answer 2

By making use of \begin{align} F_{n} = \frac{\alpha^{n} - \beta^{n}}{\alpha - \beta} \end{align} where $2 \alpha = 1+ \sqrt{5}$ and $2 \beta = 1 - \sqrt{5}$, then \begin{align} \sum_{n=0}^{\infty} F_{2n} \, x^{2n} &= \frac{1}{\alpha - \beta} \, \left( \frac{1}{1-\alpha^{2} x^{2}} - \frac{1}{1 - \beta^{2} x^{2}} \right) = \frac{F_{2} \, x^{2}}{1 - L_{2} x^{2} + x^{4}} \end{align} where $L_{n}$ are the Lucas numbers.

By using the difference equation $F_{2n+4} = a F_{2n+2} + b F_{2n}$ then \begin{align} \sum_{n=0}^{\infty} F_{2(n+2)} \, x^{2n} &= a \sum_{n=0}^{\infty} F_{2(n+1)} \, x^{2n} + b \sum_{n=0}^{\infty} F_{2n} \, x^{2n} \\ \sum_{n=2}^{\infty} F_{2n} \, x^{2n-4} &= a \sum_{n=1}^{\infty} F_{2n} \, x^{2n-2} + b \sum_{n=0}^{\infty} F_{2n} \, x^{2n} \\ \frac{1}{x^{4}} \, \left( - F_{2} x^{2} + \frac{F_{2} x^{2}}{1 - L_{2} x^{2} + x^{4}} \right) &= \frac{a}{x^{2}} \, \frac{F_{2} \, x^{2}}{1 - L_{2} x^{2} + x^{4}} + \frac{b \, F_{2} \, x^{2}}{1 - L_{2} x^{2} + x^{4}} \\ \end{align} which becomes $F_{2} L_{2} x^{4} - F_{2} x^{6} = a F_{2} x^{4} + b F_{2} x^{6}$ and leads to $a = L_{2} = 3$ and $b = -1$. This can be verified in the following way: \begin{align} 3 F_{2n-2} - F_{2n-4} &= 3 F_{2n-2} - ( F_{2n-2} - F_{2n-3} ) \\ &= F_{2n-1} + F_{2n-2} \\ &= F_{2n} \end{align} which is the desired result.