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

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

• You can do it fairly mechanically using Binet's formula $F_n = \frac{\phi^n - \varphi^n}{\phi - \varphi}$, although you might consider that cheating. More interesting might be to find a combinatorial proof. – Qiaochu Yuan Mar 10 '19 at 21:58
• This sequence satisfies the recurrence relation $a_{n+4} - 4a_{n+3} - 19a_{n+2} - 4a_{n+1} + a_{n} + 5 = 0$. – Chip Hurst Mar 11 '19 at 0:01
• @ChipHurst how have you derived that? – Qiang Li Mar 11 '19 at 2:11

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}$$