GCD of Consecutive Integers of General Fibonacci Sequence

From ProofWiki
Jump to navigation Jump to search

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$


Sources