4
$\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$
2
  • 2
    $\begingroup$ Hint: If $F(x)$ is the generating function for the Fibonacci numbers, then $F_{even}(x) = (F(x) + F(-x))/2$. $\endgroup$ Commented Jun 13, 2015 at 2:24
  • $\begingroup$ $F_\text{even}(x)=\dfrac{x^2}{x^4-3x^2+1}$ $\endgroup$ Commented Jun 13, 2015 at 2:46

2 Answers 2

Reset to default
7
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.