Fantastic Fibonacci: Newbie at Number Theory and Let’s Get Real… Analysis Team Up

We spent a long time in our Newbie as Number Theory series, as well as some time in our current Let’s Get Real… Analysis series. Today, we will use tools from number theory and analysis to learn a little about the incredible Fibonacci numbers! But first, let’s define what they are just in case you haven’t seen them before!

Definition (Fibonacci Numbers): We will define the Fibonacci numbers, denoted $F_n.$ First, define $F_1:= 1$ and $F_2 := 1$ . Now inductively define,

$F_{n+1}:= F_{n}+F_{n-1}.$

Using this definition, we can write out some of the first Fibonacci numbers,

$F_{n}\;:\; 1\,,\,1\,,\,2\,,\,3\,,\,5\,,\,8\,,\,13\,,\,21\,,\,34\,,\,55\,,\,89\,,\,144\,,\,233\,,\,377\cdots$

A Number Theory Fact

Our plan is to deduce some number theory-esc properties and then end with a property that uses analysis.

Proposition (Fibonacci GCDs): Any two consecutive Fibonacci numbers are relatively prime, that is,

$\gcd{(F_{n+1},F_{n})} = 1$

for all $n\in \mathbb{N}$ .

Proof: (Click in the Discovery)

We do this by induction on $n.$ Looking back at our list of the 14 Fibonacci numbers we see that $\gcd{(F_2,F_{1})} =\gcd{(1,1)} = 1$ completing our base case. Now let’s assume that $\gcd{(F_{n+1},F_{n})} = 1$ for some $n\in \mathbb{N}.$ We aim to prove that $\gcd{(F_{n+2},F_{n+1})} = 1.$ With goal in mind, observe that

$F_{n+2}= F_{n+1}+F_{n},$

by defintion. Thus, we need to deteremine

$\gcd{(F_{n+1}+F_{n},F_{n+1})} .$

Which, using our results from Newbie at Number Theory: (Part 3) ax+by=1, we are motivated to find an integer solution to the equation

$\Big(F_{n+1}+F_{n}\Big)\cdot x + F_{n+1} y = 1.$

Since finding a solution will prove $\gcd{(F_{n+2},F_{n+1})} = 1.$

By our induction hypothesis we know that there is an integer solution to the equation $F_{n} x' + F_{n+1} y' = 1.$ Let’s denote this solution,

$F_{n} x_0 + F_{n+1} y_0 = 1.$

Adding and subtracting $x_0$ to $y_0$ gives,

$F_{n} x_0 + F_{n+1}\Big( y_0+x_0-x_0\Big) = 1.$

Which we can rearrange to obtain,

$\Big(F_{n+1}+F_{n}\Big)\cdot x_0 + F_{n+1} \cdot \Big( y_0-x_0\Big) = 1.$

Which is a solution to $\Big(F_{n+1}+F_{n}\Big)\cdot x + F_{n+1} y = 1.$ , namely $x = x_0$ and $y= y_0 - x_0.$ Thus, we have the integer solution to,

$F_{n+2}x+ F_{n+1} y= 1,$

which proves that $\gcd{(F_{n+2},F_{n+1})} = 1,$ closing the induction.¹

$\square$

An Analysis Result

Theorem (The Golden Ratio): The ratio of consecutive Fibonacci numbers converges to a number called the golden ratio. More precisely,

$\lim_{n \rightarrow \infty} \frac{ F_{n+1} }{ F_{n} } = \varphi =\frac{1 + \sqrt{5}}{2}$

Where $\varphi = \frac{1 + \sqrt{5}}{2}$ is the golden ratio.

Proof: (Click in the Discovery)

Define the sequence $a_n:= \frac{ F_{n} }{ F_{n-1} }$ for clarity.

We will use my favorite theorem from elementary real analysis: The monotone convergence theorem, twice! Will be showing three things; (i) the subsequences $(a_{2n})$ is monotone decreasing and bounded below, (ii) the subsequence $(a_{an+1})$ is monotone increasing and bounded above, and (iii) if $(a_{2n})$ converges to $\varphi$ and $(a_{2n+1})$ converges to $\varphi$ , then $(a_n)$ converges to $\varphi.$

(ia) Monotone Decreasing: $a_{2n} =\frac{F_{2n}}{F_{2n-1}}\leq \frac{F_{2n+2}}{F_{2n+1}} = a_{2(n+1)}.$

We will prove the equivalent statement: $F_{2n}F_{2n+1}\leq F_{2n+2}F_{2n-1}$ using induction on $n.$ Our base case is the statement: $F_2F_3 = 1(2) \leq 3(1) = F_4F_1.$ Now assume that $F_{2n}F_{2n+1}\leq F_{2n+2}F_{2n-1}$ for some $n.$ Consider $F_{2n+4}F_{2n+1},$ all we are going to do is repeatedly use the definition of $F_{n}$ ,

$F_{2n+4} F_{2n+1} = \Big( F_{2n+3} + F_{2n+2} \Big) \Big( F_{2n}+F_{2n-1} \Big) \\ \textit{ }\qquad\qquad\;\,= F_{2n+3} \Big( F_{2n} +F_{2n-1} \Big) + F_{2n+2} F_{2n} + F_{2n+2}F_{2n-1} \\ \textit{ }\qquad\qquad\;\,\geq F_{2n+3} \Big( F_{2n}+F_{2n-1}\Big) + F_{2n+2}F_{2n} + F_{2n}F_{2n+1} \qquad \qquad \mathrm{by}\;\mathrm{induction}\;\mathrm{hypothesis}\\ \textit{ }\qquad\qquad\;\,= F_{2n+3}\Big(F_{2n+1}\Big) + F_{2n+3}F_{2n}\\ \textit{ }\qquad\qquad\;\,= F_{2n+3}F_{2n+2}$

completing the induction.

(ib) Bounded Below: $a_{2n} \geq 0.$

Clearly each Fibonacci number is positive, and since the ratio of two positive numbers is positive, we have $a_{2n} \geq 0.$

Thus, $a_{2n}$ converges by the monotone convergence theorem. Let’s denote $a_{2n}$ s limit by $x.$

$a_{2n}\rightarrow x.$

(iia) & (iib) Left as an exercises, you’re welcome!

(iiia) We will first prove that $a_{2n}\rightarrow \varphi$ and $a_{2n+1}\rightarrow \varphi$ .

By parts (i) and (ii), we concluded that both $a_{2n}$ and $a_{2n+1}$ converge by the monotone convergence theorem. We will now find what they converge to.

Let’s begin by focusing on $a_{2n+2} =\frac{F_{2n+2}}{F_{2n+1}}.$ Using the definition of the Fibonacci numbers (again) we have,

$\frac{ F_{2n+2} }{F_{2n+1}} = \frac{F_{2n+1}+F_{2n} }{F_{2n+1}} = 1 +\frac{F_{2n}}{F_{2n+1}} = 1 + \frac{F_{2n}}{F_{2n} + F_{2n-1}}=1 + \frac{1}{1 +\frac{ F_{2n-1}}{F_{2n}}} = 1+\frac{1}{1 +\frac{ 1}{a_{2n}}}.$

Thus $a_{2n+2} =1+\frac{1}{1 +\frac{ 1}{a_{2n}}}.$ Furthermore, since $a_{2n}\rightarrow x,$ it’s also the case that $a_{2n+2}\rightarrow x,$ (see here). It then follows, using limit arithmetic laws. that,

$1+\frac{1}{1 +\frac{ 1}{a_{2n}}}\rightarrow 1 +.\frac{1}{1+1/x}$

Hence $x= 1 +\frac{1}{1+1/x}.$ A quick use of the quadratic formula (or completing the square) gives two solutions: $x_{\pm} = \frac{1 \pm \sqrt{5}}{2}.$ However, $x_{-}<0.$ We already showed in (ib) that $a_{2n}>0.$ Thus, $a_{2n} \rightarrow x_+ = \frac{1 + \sqrt{5}}{2} = \varphi.$

(iiib) A similar argument shows that $a_{2n+1} \rightarrow \frac{1 + \sqrt{5}}{2}= \varphi.$

(iiic) Since both $a_{2n} \rightarrow \varphi$ and $a_{2n+1} \rightarrow \varphi.$ We claim that $a_{n} \rightarrow \varphi.$ Indeed, let $\varepsilon>0$ and since $a_{2n} \rightarrow \varphi,$ there exists some $N_1$ such that $|a_{2n} - \varphi|<\varepsilon$ for all $n>N_1.$ Likewise, since $a_{2n+1} \rightarrow \varphi,$ there exists some $N_2$ such that $|a_{2n_1} - \varphi|<\varepsilon$ for all $n>N_2.$ Let $N = \max{(N_1,N_2)}.$ Then, we have

$|a_{n} - \varphi|<\varepsilon,$

for all $n>N.$ (Can you see why?)

Thus, we have shown that $a_{n} \rightarrow \varphi$ as desired.

$\square$

Remark: I would like to make explicit that the golden ratio $\varphi$ is the solution to the quadratic equation: $x^2 = x+1.$ Hence, $\varphi^2 = \varphi+1.$ We will use this in the next theorem.

More Golden Ratio

We’ve learned that the ratio of consecutive Fibonacci numbers converges to the golden ratio $\varphi = \frac{1 + \sqrt{5}}{2}.$ We will now show that we can use powers of the golden ratio to find Fibonacci numbers.

Theorem (Fibonacci as Coefficients): $\varphi^n = F_n \varphi + F_{n-1}.$

Proof: (Click in the Discovery)

We proceed by induction on $n$ .

Our base case is the statement:² $\varphi^2 = F_2 \varphi + F_{1} = \varphi + 1$ which is what we said in the remark earlier. Assume that $\varphi^n = F_n \varphi + F_{n-1}.$ Now we must show $\varphi^{n+1} = F_{n+1} \varphi + F_{n}.$ To this end,

$\varphi^{n+1} = \varphi^n \varphi \\ \text{ }\;\;\;\;\;\,= (F_n \varphi + F_{n-1}) \varphi \qquad \qquad \mathrm{by}\;\mathrm{induction}\;\mathrm{hypothesis}\\ \text{ }\;\;\;\;\;\,= F_n \varphi^2 + F_{n-1}\varphi \\ \text{ }\;\;\;\;\;\,=F_n (\varphi+1) + F_{n-1}\varphi \qquad \qquad \mathrm{since}\;\varphi^2 = \varphi+1\\ \text{ }\;\;\;\;\;\,= (F_n +F_{n-1})\varphi+ F_n \\ \text{ }\;\;\;\;\;\,= F_{n+1}\varphi+F_n.$

Closing the induction. Thus, $\varphi^n = F_n \varphi + F_{n-1}.$

$\square$

There’s So Much Amazing Math Left

Due to the Fibonacci numbers popularity, there is so much great math(s) out there regarding them! For instance, did you know that the Fibonacci numbers show up in Pascal’s triangle? Or that the Fibonacci numbers are deeply related to the Pythagorean theorem (see the video below)? To quote the great Richard Feynman in the popular BBC series FUN TO IMAGINE, “I gotta stop somewhere. I’ll leave you something to imagine.” Until next time!

Here’s Mathologer’s video showing the connection between Fibonacci numbers and the Pythagorean theorem: Fibonacci = Pythagoras: Help save a beautiful discovery from oblivion

Oh, and here’s last week’s article on the Pythagorean theorem.

Be Kind. Be Curious. Be Compassionate. Be Creative.

And Have Fun!

Footnotes.

You can use a similar procedure to prove the following result: If $\gcd{(a,b)} = d$ and $\gcd{(b,c)} = d,$ then $\gcd{(a,c)} = d.$ ↩︎
The way we defined the Fibonacci numbers, has $F_1 = 1$ as the first Fibonacci number. However, if needed, some people define the first Fibonacci number to be $F_0 :=0.$ If we chose to define them this way, our base case would have been $\varphi^1 = F_1 \varphi + F_{0}.$ ↩︎

A Kick in the Discovery