GCD of Consecutive Integers of General Fibonacci Sequence

Theorem

Let $\FF = \sequence {a_n}$ be a general Fibonacci sequence generated by the parameters $r, s, t, u$:

$a_n = \begin{cases} r & : n = 0 \\ s & : n = 1 \\ t a_{n - 2} + u a_{n - 1} & : n > 1 \end{cases}$

Let:

$d = \gcd \set {r, s}$

where $\gcd$ denotes greatest common divisor.

Let $f = \gcd \set {a_m, a_{m - 1} }$ for some $m \in \N$.

Let $\gcd \set {f, t} = 1$.

Then:

$f \divides d$

Proof

Proof by induction:

Let $\map P m$ be the proposition:

$\gcd \set {f_m, t} = 1 \implies f_m = d$

where $f_m = \gcd \set {a_m, a_{m - 1} }$.

For clarity, we have indexed $f$.

Basis for the Induction

For $m = 1$:

$f_1 = \gcd \set {a_1, a_0} = \gcd \set {s, r} = d$

This is the basis for the induction.

Induction Hypothesis

Now we assume that $\map P k$ is true for some $k \in \N$.

In other words, this is our induction hypothesis:

$\gcd \set {f_k, t} = 1 \implies f_k = d$

where $f_k = \gcd \set {a_k, a_{k - 1} }$.

Now we need to show that $\map P {k + 1}$ is true, that is:

$\gcd \set {f_{k + 1}, t} = 1 \implies f_{k + 1} = d$

where $f_{k + 1} = \gcd \set {a_{k + 1}, a_k}$.

Induction Step

This is our induction step:

 $\ds f_{k + 1}$ $=$ $\ds \gcd \set {a_{k + 1}, a_k}$ $\ds$ $=$ $\ds \gcd \set {t a_{k - 1} + u a_k, a_k}$ Definition of $\sequence {a_n}$ $\ds$ $=$ $\ds \gcd \set {t a_{k - 1}, a_k}$ GCD with Remainder $\ds$ $=$ $\ds \gcd \set {t, a_k} \gcd \set {a_{k - 1}, a_k}$ GCD with One Fixed Argument is Multiplicative Function $\ds$ $=$ $\ds \gcd \set {t, a_k} f_k$

Suppose that $\gcd \set {f_{k + 1}, t} = 1$.

Then:

 $\ds 1$ $=$ $\ds \gcd \set {f_{k + 1}, t}$ $\ds$ $=$ $\ds \gcd \set {\gcd \set {t, a_k}, t}$ Divisor of One of Coprime Numbers is Coprime to Other $\ds$ $=$ $\ds \gcd \set {t, \gcd \set {t, a_k} }$ Greatest Common Divisor is Symmetric $\ds$ $=$ $\ds \gcd \set {\gcd \set {t, t}, a_k}$ Greatest Common Divisor is Associative $\ds$ $=$ $\ds \gcd \set {t, a_k}$ GCD of Integer and Divisor

By the two results above, we have:

$f_{k + 1} = \gcd \set {t, a_k} f_k = f_k$

so we have $\gcd \set {f_k, t} = \gcd \set {f_{k + 1}, t} = 1$ as well.

By the induction hypothesis and Modus Ponendo Ponens:

$f_k = d$

and thus:

$f_{k + 1} = f_k = d$

so $\map P {k + 1}$ is true.

By the Principle of Mathematical Induction, $\map P m$ is true for all $m \in \N$.

Hence the result.

$\blacksquare$