Investigating Bezout's Identity for Fibonacci Numbers

The Fibonacci numbers: \( 1,1,2,3,5,8,13,21,... \) have a number of interesting properties. A few days ago, I discovered and proved one such property that I find particularly interesting. It turns out that successive Fibonacci numbers are always relatively prime (I will prove this later). Further, Bezout's lemma guarantees the existence of integers \( p \) and \( q \) such that \( p F_n + q F_{n+1} = 1 \), where \( F_n \) denotes the \( n^{th} \) number in the Fibonacci sequence. In this blog post, I will find a general formula for \( p \) and \( q \). There is a simple result and an elegant proof of that result which I will demonstrate.

Before we find a general formula for \( p \) and \( q \), let me first prove that \( F_n \) and \( F_{n+1} \) are always relatively prime:

Assume for contradiction that \( F_n \) and \( F_{n+1} \) have a factor, \( d > 1 \) that they share. Then \( F_n = d k_1 \) and \( F_{n+1} = d k_2 \) for some integers \( k_1 \) and \( k_2 \). Further, by definition of the recurrence relation, we know \( F_{n+1} = F_n + F_{n-1} \) or equivalently \( F_{n-1} = F_{n+1} - F_n \). Thus, \( F_{n-1} = d k_2 - d k_1 = d (k_2 - k_1) \). This implies \( F_{n-1} \) and \( F_n \) have \( d \) as a common factor, which indicates that d is divisor of all numbers in the sequence, which is a contradiction since \( F_0 = 1 \) has no divisors greater than \( 1 \).

I've shown that successive terms in the Fibonacci sequence are relatively prime. Now I will find the Bezout identity relating the successive terms; that is, I will find \( p \) and \( q \) such that \( p F_n + q F_{n+1} = 1 \). Let's consider a few examples:
$$ \begin{align*}
F_5 p + F_6 q &= 1 & F_8 p + F_9 q &= 1 \\
8 p + 13 q &= 1  & 34 p + 55 q &= 1 \\
8 (5) + 13 (-3) &= 1 & 34(-21) + 55 (13) &= 1 \\
F_5 F_4 - F_6 F_3 &= 1 & -F_8 F_7 + F_9 F_6 &= 1
\end{align*} $$ Notice anything interesting? In these examples, \( p \) and \( q \) are just Fibonacci numbers. More specifically, they are the previous two Fibonacci numbers (the next two Fibonacci numbers work as well - the Bezout identity is not unique). Also, it looks like the order of the terms switches depending on the parity of \( n \). I conjecture (and will prove) that
 $$ \begin{cases} &F_{n+3} F_n - F_{n+2} F_{n+1} = 1 \hfill & \text{ if $n$ is even} \\ -&F_{n+3} F_n + F_{n+2} F_{n+1} = 1 \hfill & \text{ if $n$ is odd} \\ \end{cases} $$
In order to prove this, I will use the Fibonacci recurrence to re-write
$$
F_{n+3} F_n - F_{n+2} F_{n+1}
$$ in terms of only \( F_{n+1}, F_{n+2}, F_{n+3}, \) and \( F_{n+4} \). Since \( F_{n+2} = F_{n+1} + F_n \), we know \( F_n = F_{n+2} - F_{n+1} \). Substituting into the above equation (in multiple places), we get
$$ F_{n+3} (F_{n+2} - F_{n+1}) - (F_{n+4} - F_{n+3}) F_{n+1} \\
F_{n+3} F_{n+2} - F_{n+3} F_{n+1} - F_{n+4} F_{n+1} + F_{n+3} F_{n+1} \\
F_{n+3} F_{n+2} - F_{n+4} F_{n+1} $$  I have shown that
$$
F_{n+3} F_n - F_{n+2} F_{n+1} = F_{n+3} F_{n+2} - F_{n+4} F_{n+1}
$$ This is a fascinating result, and since my conjecture holds for \( n = 0 \):
$$
F_3 F_0 - F_2 F_1 = 3 (1) - 2 (1) = 1
$$ it also holds for all \( n \)!
$$ \begin{align*}
F_3 F_0 - F_2 F_1 &= 1 \\
-F_4 F_1 + F_3 F_2 &= 1 \\
F_5 F_2 + F_4 F_3 &= 1 \\
 -F_6 F_3 - F_5 F_4 &= 1 \\
& \vdots
\end{align*} $$

Comments

Popular posts from this blog

Multi-Core Programming with Java

Beat the Streak: Day Three

Interpolation Search Explained