Proof of ${F(n+4)}^{4} - {4F(n+3)}^{4} - {19F(n+2)}^{4} - {4F(n+1)}^{4}+{F(n)}^{4} = -6$

Question

Observe:

\begin{matrix} F(n)|&{F(n)}^{4}& - {4F(n+1)}^{4}& - {19F(n+2)}^{4}&- {4F(n+3)}^{4}&{F(n+4)}^{4}& = -6\\ 1|& 1& -4& -304& -324& 625&=-6\\ 1|& 1& -64& -1539& -2500& 4096&=-6\\ 2|& 16& -324& -11875& -16384& 28561&=-6\\ 3|& 81& -2500& -77824& -114244& 194481&=-6\\ 5|& 625& -16384& -542659& -777924& 1336336&=-6\\ 8|& 4096& -114244& -3695139& -5345344& 9150625&=-6 \end{matrix}

I see that the proof is true but I cant quite grasp the pattern. I'm more interested in hints rather than a solution. Ive read through this website about Fibonomials a couple times and have a decent understanding but I cant figure how to apply it in this situation. It may not even be necessary. I've tried proving through induction but ended up with almost exactly the same problem. I think there may be a proof through some sort of recursive sequence but I don't know enough to prove something like that.

I'm more interested in hints rather than a solution.

Answer 1

This is not the most elegant solution, but its a very straight forward computation using the standard tools we use to solve recurence-relations.

Let $a_n = F_n^4$ (where $F_n$ represents the terms in your recurence relation which we don't yet know is the Fibonacci sequence) then $$a_{n+4} - 4a_{n+3} - 19a_{n+2} - 4a_{n+1} + a_n = -6$$

The characteristic polynomial is

$$x^4 - 4x^3 - 19x^2 - 4x + 1 = (x^2+3x+1)(x^2-7x+1)$$

The particular solution is $a_n = C = \frac{6}{25}$ so the full solution reads

$$a_n = \frac{6}{25} + a r_+^n + b r_-^n + c s_+^n + d s_-^n$$

where

$$r_\pm = \frac{-3 \pm \sqrt{5}}{2} = \left(\frac{1\pm \sqrt{5}}{2}\right)^2$$ $$s_\pm = \frac{7 \pm 3\sqrt{5}}{2} = r_{\pm}^2 = \left(\frac{1\pm \sqrt{5}}{2}\right)^4$$

are the roots of the characteristic polynomial. Now note that the Fibonacci numbers statisfy

$$F_n = e\left(\frac{1+\sqrt{5}}{2}\right)^n + f\left(\frac{1-\sqrt{5}}{2}\right)^n$$

Fixing the constants $a,b,c,d,e,f$ gives us $a_n = F_n^4$ where $F_n$ here is the Fibonacci sequence.

${\bf Added}:$

Defining $q_\pm = \frac{1\pm\sqrt{5}}{2}$ then $$F_n = \frac{1}{\sqrt{5}}(q_+^n - q_-^n)$$ so

$$F_n^4 = \frac{1}{25}\left((q_+^4)^n + (q^4_-)^n + 4(q_+^3 q_-)^n + 6 (q^2_- q^2_+)^n + 4(q_+q_-^3)^n\right)$$

Now we use $q_+q_- = -1$ to find

$$F_n^4 = \frac{1}{25}\left((q_+^4)^n + (q^4_-)^n - 4(q_+^2)^n - 4(q_-^2)^n + 6\right)$$

or using the notation $s_\pm,r_\pm$ defined above we have

$$F_n^4 = \frac{1}{25}\left(s^n_+ + s^{n}_{-} -4r^{n}_{+} - 4r^{n}_{-} + 6\right)$$

which gives $a=b=-\frac{4}{25}$ and $c=d=\frac{1}{25}$.

Answer 2

Here is a fun theorem that's useful for these types of problems: For any integers $d$ and $k$ there exists an integer $N$ such that for any polynomial $p(x_1,x_2,...x_k)$ of degree $d$, $p(F_n,F_{n+1},...,F_{n+k-1})=0$ for $n = 0,1,2, ... ,N$ implies $p(F_n,F_{n+1},...,F_{n+k-1})=0$ for all $n$.

In your case $d = 4$ and $k = 5$. Depending on how carefully you go through the proof of this theorem you can get $N$ down to say 100 pretty easily, and down to around 18 with a little more work (if my mental calculations are correct). Either way you can have a computer check that many values pretty easily.

Answer 3

Okay, let me give some hints by gesturing at a few things.

On the left-hand side, we have an operator of the form $X^4 - 4X^3 - 19X^2 - 4X + 1 = (X^2-7 X+1) (X^2+3 X+1)$ applied to the sequence $F(n)^4$.

Let $\phi = \frac{1+\sqrt{5}}{2}$, the positive root of the characteristic equation for the Fibonacci recurrence.

Interestingly enough, $X^2-7 X+1$ is the minimal polynomial for $\phi^4$, and $X^2 + 3X + 1$ is the minimal polynomial for $-\phi^2$. These things are not coincidences.

If the extremely abstract approach doesn't appeal to you, here's a merely very abstract view: think about the identity $5F_n^2 = L_{2n} + 2\cdot(-1)^n$. The right-hand side satisfies some recursion related to the Fibonacci sequence. If you can make sense of this fact, and generalize it to $F_n^4$, you're in the home stretch.

Answer 4

You already have an accepted answer, but here is an alternative approach.

$${F(n+4)}^{4} - {4F(n+3)}^{4} - {19F(n+2)}^{4} - {4F(n+1)}^{4}+{F(n)}^{4}$$

reduces to $$-6\left(F(n+1)^2 - F(n+1)F(n) - F(n)^2\right)^2$$

by applying Fibonacci recursion.

So what's left to prove is that

$$F(n+1)^2 - F(n+1)F(n) - F(n)^2 \in \{1, -1\}$$

or more specifically:

$$F(n+1)^2 - F(n+1)F(n) - F(n)^2 = \begin{cases} +1 \text{ for } 2\mid n \\ -1 \text{ for } 2\not\mid n \\ \end{cases}$$

which follows inductively, given

$$\begin{align} & F(n+1)^2 - F(n+1)F(n) - F(n)^2\\ &= F(n+1)\bigg(F(n+1) - F(n)\bigg) - F(n)^2 \\ &= \bigg(F(n) + F(n-1)\bigg)F(n-1) - F(n)^2 \\ &= -\left(F(n)^2 - F(n)F(n-1) - F(n-1)^2\right) \end{align}$$