GCD of Generators of General Fibonacci Sequence is Divisor of All Terms

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.

Then:

$\forall n \in \Z_{>0}: d \divides a_n$

Proof

From the construction of a general Fibonacci sequence, $a_n$ is an integer combination of $r$ and $s$.

From Set of Integer Combinations equals Set of Multiples of GCD, $a_n$ is divisible by $\gcd \set {r, s}$.

Hence the result.

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Exercise $12 \ \text{(a)}$