Can we tell from the generating function of the Fibonacci sequence that the generating function of the squared sequence is rational?

52 Views Asked by At

The formal power series of the Fibonacci sequence is given by $$ \sum_{n \geq 0} f_nq^n=q+q^2+2q^3+3q^4+5q^5+\cdots $$ whereby $f_n=f_{n-1}+f_{n-2}$ denotes the $n$-th Fibonacci number. Its closed form, call it $\Phi(q)$, is given by

$$ \Phi(q)=\frac{q}{1-q-q^2} $$

The function $\Phi(q)$ is rational. We can see this by just calculating the above or by knowing the following theorem.

Theorem: The ordinary generating function of a sequence can be expressed as a rational function if and only if the sequence is a linear recurrence relation.

Now, consider the sequence $a_n=f_n^2$. The generating function of $a_n$ is given by the following formal power series.

$$ \sum_{n \geq 0} f_n^2q^n=f_1^2q + f_2^2q^2+f_3^2q^3+\cdots $$

I want to show that $\Phi'(q)$ is rational without calculating its closed form.

My approach: We can show that the sum of squares of consecutive Fibonacci numbers is a Fibonacci number namely $f_n^2 + f_{n+1}^2=f_{2n+1}=f_{2n}+f_{2n-1}$, thus the sequence $a_n$ is a linear recurrence relation. By applying the above theorem, we are done.

Question: Can we tell from the closed form $\Phi(q)$ of the generating function of the usual Fibonacci sequence that $\Phi'(q)$ is rational? If not, is there a different approach for showing that $\Phi'(q)$ is rational without actually calculating it?