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

  1. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.


    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals


    ReplyDelete
  2. Certified Management Accountant is one of the most important professions nowadays. They are a great help in the business industry because they have the skills to improve the efficiency of management and operation in a certain business firm.They can also do effective analysis for the development of a certain business.


    Anyone can be a Certified Management Accountant if you have done the specific requirements to become a CMA. Primarily, finishing your degree in CMA is the first thing to do to become one of the management accountants in the world.

    ReplyDelete

  3. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.
    <a href=" http://letslearngroup.com/cpa-training</a>

    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals



    ReplyDelete
  4. Certified Management Accountant is one of the most important professions nowadays. They are a great help in the business industry because they have the skills to improve the efficiency of management and operation in a certain business firm.They can also do effective analysis for the development of a certain business.
    <a href=" http://letslearngroup.com/cma-training</a>

    Anyone can be a Certified Management Accountant if you have done the specific requirements to become a CMA. Primarily, finishing your degree in CMA is the first thing to do to become one of the management accountants in the world.

    ReplyDelete

  5. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.
    <a href=" http://letslearngroup.com/cpa-training</a>

    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals


    ReplyDelete

  6. Certified Management Accountant is one of the most important professions nowadays. They are a great help in the business industry because they have the skills to improve the efficiency of management and operation in a certain business firm.They can also do effective analysis for the development of a certain business.
    <a href=" http://letslearngroup.com/cma-training</a>

    Anyone can be a Certified Management Accountant if you have done the specific requirements to become a CMA. Primarily, finishing your degree in CMA is the first thing to do to become one of the management accountants in the world.

    ReplyDelete
  7. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.
    <a href=" http://letslearngroup.com/cpa-training</a>

    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals



    ReplyDelete
  8. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.
    <a href=" http://letslearngroup.com/cpa-training</a>

    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals



    ReplyDelete
  9. Certified Management Accountant is one of the most important professions nowadays. They are a great help in the business industry because they have the skills to improve the efficiency of management and operation in a certain business firm.They can also do effective analysis for the development of a certain business.
    Anyone can be a Certified Management Accountant if you have done the specific requirements to become a CMA. Primarily, finishing your degree in CMA is the first thing to do to become one of the management accountants in the world.

    ReplyDelete

  10. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.
    <a href=" http://letslearnglobal.com/cpa/</a>

    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals

    ReplyDelete
  11. Certified Management Accountant is one of the most important professions nowadays. They are a great help in the business industry because they have the skills to improve the efficiency of management and operation in a certain business firm.They can also do effective analysis for the development of a certain business.
    <a href=" http://letslearngroup.com/cma-training</a>

    Anyone can be a Certified Management Accountant if you have done the specific requirements to become a CMA. Primarily, finishing your degree in CMA is the first thing to do to become one of the management accountants in the world.

    ReplyDelete

  12. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.
    <a href=" http://letslearngroup.com/cpa-training</a>

    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals




    ReplyDelete
  13. Hey I am for the first time here. I came across this blog and I find It really useful & it helped me out much. I hope to give something back and aid others like you helped me. I think this is engaging and eye-opening material. Thank you so much for caring about your content and your readers.
    Visit:
    Download asphalt 8 mod apk
    Download S Photo Editor Pro APK
    Download shadow fight 3 unlimited money

    ReplyDelete
  14. Certified Management Accountant is one of the most important professions nowadays. They are a great help in the business industry because they have the skills to improve the efficiency of management and operation in a certain business firm.They can also do effective analysis for the development of a certain business.
    http://letslearnglobal.com/cma/


    Anyone can be a Certified Management Accountant if you have done the specific requirements to become a CMA. Primarily, finishing your degree in CMA is the first thing to do to become one of the management accountants in the world.

    ReplyDelete
  15. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.
    <a href=" http://letslearngroup.com/cpa-training</a>

    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals

    ReplyDelete
  16. CPA is a globally recognized financial course offered by AICPA (The American Institute of Public Accountants ) USA.


    A CPA is a trusted financial advisor who helps individuals, businesses, and other organizations plan and reach their financial goals

    ReplyDelete
  17. Certified Management Accountant is one of the most important professions nowadays. They are a great help in the business industry because they have the skills to improve the efficiency of management and operation in a certain business firm.They can also do effective analysis for the development of a certain business.
    http://letslearnglobal.com/cma/


    Anyone can be a Certified Management Accountant if you have done the specific requirements to become a CMA. Primarily, finishing your degree in CMA is the first thing to do to become one of the management accountants in the world.

    ReplyDelete
  18. This is an awesome post with good information. ola Customer Care Number

    ReplyDelete

Post a Comment

Popular posts from this blog

Multi-Core Programming with Java

Efficiently Remove Duplicate Rows from a 2D Numpy Array

Beat the Streak: Day Three