3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hint: If $F(x)$ is the generating function for the Fibonacci numbers, then $F_{even}(x) = (F(x) + F(-x))/2$. $\endgroup$ – Slade Jun 13 '15 at 2:24
  • $\begingroup$ $F_\text{even}(x)=\dfrac{x^2}{x^4-3x^2+1}$ $\endgroup$ – Lucian Jun 13 '15 at 2:46
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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