# Generalized Fibonacci Sequence

I'm having trouble with a problem I encountered while studying Number Theory. This problem comes from the book Number Theory by George E. Andrews.

It defines a generalized Fibonacci sequence $F_1$, $F_2$, $...$ by selecting four integers $a,b,c,e$ and defining $F_1 = a$, $F_2 = b$, and for all $n > 2$, $F_n = cF_{n-1} + eF_{n-2}$.

Define $d = \gcd(a,b)$ and $f = \gcd(F_m, F_{m-1})$.

It asks to prove that if $\gcd(f,e) = 1$, then $f | d$.

Since $F_n=cF_{n-1}+eF_{n-2}$, if the greatest common divisor of $F_n$ and $F_{n-1}$ does not divide $e$, it must divide $F_{n-2}$. So $f$ divides both $F_{n-1}$ and $F_{n-2}$ but not $e$, hence it must divide $F_{n-3}$. By going backwards, $f$ must divide both $F_1$ and $F_2$, hence it must divide their greatest common divisor. This proves $f|d$.