generating function for $F_{5n}/(5F_n)$

Question

Let $F_n$ be the $n$-th Fibonacci number with $F_0=0$, $F_1=1$, and $F_k=F_{k-1}+F_{k-2}$ for $k\ge2$. Prove $$\sum^{\infty}_{n=0}{a_nx^n}=\frac{1-4x-9x^2+6x^3+x^4}{1-5x-15x^2+15x^3+5x^4-x^5}$$ where $a_n=F_{5n}/(5F_n).$

Answer 1

This seems quite tough so I'm thinking you must have some results from a course text book that are relevant. Anyway, tackling it from the back end, the given generating function's denominator can be factorised;

$$\frac{1-4x-9x^2+6x^3+x^4}{1-5x-15x^2+15x^3+5x^4-x^5}$$ $$=\frac{1-4x-9x^2+6x^3+x^4}{(x^2-7x+1)(x^2+3x+1)(1-x)}$$ and then partial fractions yield, $$\frac{2-7x}{5(x^2-7x+1)}+\frac{3x+2}{5(x^2+3x+1)}+\frac{1}{5(1-x)}$$ These quadratic denominators in a generating function scream Fibonacci; $$\frac{1}{x^2+3x+1}$$ $$=1-3x+8x^2-21x^3+55x^4-144x^5+\dots$$ $$=F_2-F_4x+F_6x^2-F_8x^3+F_{10}x^4-F_{12}x^5+\dots$$ and $$\frac{1}{x^2-7x+1}$$ $$=1+7x+48x^2+329x^3+2255x^4+15456x^5+105937x^6+726103x^7+\dots$$ $$=\frac{F_4}{3}+\frac{F_8}{3}x+\frac{F_{12}}{3}x^2+\frac{F_{16}}{3}x^3+\frac{F_{20}}{3}x^3+\dots$$ and these and their ilk in themselves would be interesting to explore.

Moving to the front end, $F_{5n}$ is always a multiple of 5, so I can see why the 'divide by 5' is in there, and it's in the partial fraction decomposition too. This can be proved by induction, and is a well known result; e.g. http://www.math.utep.edu/Faculty/duval/class/2325/104/fib.pdf

The $F_{5n}$ can be broken down into an expression involving $F_n$ and $F_{n+1}$ with the neat algorithm on page four on the following document; http://www.maths.qmul.ac.uk/~pjc/comb/ch4s.pdf

Wikipedia has this decomposition for $F_{4n}$ $$F_{4n}=4F_nF_{n+1}(F_{n+1}^2+2F_n^2)-3F_n^2(F_n^2+2F_{n+1}^2)$$ I found an $F_{5n}$ decomposition (Falcon, Plaza 2007) as; $$F_{5n}=F_{n+1}^5+4F_n^5-F_{n-1}^5+10F_{n+1}F_n^3F_{n-1}$$

I don't know if that's going to help.

There is an interesting result; $$\frac{F_{kt}}{F_t}=\sum_{i=0}^{(k-3)/2}(-1)^{it}L_{(k-2i-1)}t+(-1)^{\frac{(k-1)t}{2}}$$ k is odd and > 2 and L is the Lucas number. (Vajda 85) This and 300 more Fibonacci relationships are at http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html

It may not be relevant but I note that the convolution of

$$\frac{1}{x^2+3x+1} \times \frac{1}{x^2-7x+1}$$ is $$(1.1)+(1.7+(-3).1)x+(1.48+(-3).7+8.1)x^2+(1.329+(-3).48+8.7+(-21).1)x^2$$ $$+(1.2255+(-3).329+8.48+(-21).7+55.1)x^3$$ That is $$1+4x+35x^2+220x^3+10556x^4+\dots$$ and the $\frac{1}{(1-x)}$ will be taking the partial sums of this.

Update : $F_n^4$ has the generating function $$\frac{1-4x-4x^2+x^3}{1-5x-15x^2+15x^3+5x^4-x^5}$$