Constant-recursive Fibonacci identities

Question

Under what conditions does $F_z = a F_x + b F_y$ imply $F_{z+k} = a F_{x+k} + b F_{y+k}$?

For example, $F_4 = 3 F_2 - F_0$, and $F_5 = 3 F_3 - F_1$, $F_6 = 3 F_4 - F_2$, etc.

If I can prove using the matrix form $$A^n =\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$$

that

$$A^z = a A^x + b A^y $$

then I can simply multiply by $A$.

Answer 1

I can check by hand \begin{align} F_{z} & = a F_{x} + b F_{y} \\ F_{z+1} & = a F_{x+1} + b F_{y+1} \\ \end{align}

then add the equations.

Answer 2

First some background-

• Equation - A relation between algebraic quantities (variables) which may be true for none, some or all values of the variables.

• Identity - A equation that is true for all values of the variables.

---

The relation-

Now, $F(2) \neq 2. F(3) + F(89)$ (for example), so that the relation is not an identity but simply an equation that can be solved to get values of $a$, $b$, $x$, $y$ and $z$ ( although it probably had no closed form solution ).

---

A counter example-

$F(4) = 2. F(1) + F(2)$

But, $F(5) \neq 2. F(2) + F(3)$

Therefore, the implication does not always hold and we need to find some condition(s) for which it holds.

---

An example relation (to get us on the right track)-

One such solution can be -

$$F(n) = 4. F(n-3) + F(n-6)$$

Obviously, the question of a proof by induction does not arise, as there is no recursive relation to use.

Note that, $F(n+k)$ is necessarily equal to $4.F(n-3+k) + F(n-6+k)$.

PROOF-

Our claim is -

Claim-

Given, $F(n) = 4.F(n-3) + F(n-6), \ \forall \ n\ \gt 6 in \mathbb{N}$

we have $S(k) := F(n + k) = 4.F(n-3+k) + F(n-6+k),$ is true $ \forall \ k \in \mathbb{N}$ .

Solution-

First, the base cases -

$S(0)$ is true by hypothesis.

Also, $S(1)$ is true-

$F(n+1)=4.F(n-3+1)+ F(n-6+1)$

$\Leftrightarrow \ F((n+1)) = 4. F((n+1) - 3)+F((n+1)-6)$ (The result is true for all natural $n>6$, but $n+1$ is also a natural number)

Now, it is trivial to see that -

$F(n+k)=4.F(n-3+k)+ F(n-6+k)$

$\Leftrightarrow \ F((n+k)) = 4. F((n+k) - 3)+F((n+k)-6)$

Basically, we already know the relation to be true for every natural number above 6, so the addition by $k$ can be reinterpreted as an stating the relation for the $k^(th)$ natural number after it, which is again true, since relation is true for each and every natural number (greater than 6).

We, can do the proof by mathematical induction if we want a feeling of greater rigor; but this proof is also perfectly valid and rigorous.

---

The final answer-

The above proof, suggests one condition which guarantees the property you want -

$$F(x) = a.F(y) + b.F(z) \Rightarrow F(x+k) = a. F(y+k) + b. F(z+k)$$

if $y$ and $z$ are linear functions of $x$ with coefficient of x being 1.

(Note the use of if as opposed to iff.)

That is, if an increment in $x$ automatically leads to an equal increment in $y$ and $z$.

The proof for this condition is exactly the same as the one above ( and is left to the reader :P ).

This may not necessarily be the only such condition (hence, if instead of iff), but I am unable to prove that either way.