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

  • $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Mar 10 '19 at 21:58
  • $\begingroup$ This sequence satisfies the recurrence relation $a_{n+4} - 4a_{n+3} - 19a_{n+2} - 4a_{n+1} + a_{n} + 5 = 0$. $\endgroup$ – Chip Hurst Mar 11 '19 at 0:01
  • $\begingroup$ @ChipHurst how have you derived that? $\endgroup$ – 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}$$

| cite | improve this answer | |

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.