On Binet’s Formula

R (Chandra) Chandrasekhar

2025-09-15 | 2025-10-27

Estimated Reading Time: 42 minutes

The germ of an idea

My friend Solus “Sol” Simkin and I were flying to attend a conference of a learned society in Budapest, and to kill time, were engaged in a discussion on mathematics education.

Sol said, “Mathematics has morphed rapidly and almost completely, starting from the nineteenth century, into a towering discipline built with tier-upon-tier of abstractions. And that has robbed the subject of any link with the common man, who still equates mathematics with calculation.

“Even my mathematical friends do not profess familiarity with the discipline as a whole. They are experts only in their narrow turf of specialization. The wholeness of the subject can seldom be grasped—let alone appreciated—by mathematicians, to say nothing of the physicists, engineers, and economists.”

As we rued wistfully the disappearance of generalists, I asked Sol what solution he would propose to correct the situation.

“Start small,” he said. “Take a simple problem. Examine it afresh from several angles. Approach the solution from seemingly different directions. Solve the problem. And show that all solutions coincide. Nothing will impress the young student of mathematics about the internal self-consistency of the subject—built on logic granite—than this emergence of the same solution to the one problem, tackled from different angles.

“Promise me that you would start writing along these lines so that young innocent minds are reassured that the austere subject of mathematics also hides surpassing beauty. Expose the unity of mathematics. Showcase its elegance. Highlight its awesome, almost mystical strength, wedded to its alluring charm,” Sol made his request.

“What exactly do you suggest that I should do?” I quizzed him.

“If you are keen to pick up the gauntlet, let me spell it out for you”, Sol continued. “It is a shame that when two canals are fed from the same river, the public is unaware that the water source is the same.

There are many mathematical canals which are studied separately where students do not have the slightest inkling that their origin is the same. Mathematics will become much easier if the discrete and the continuous are studied together. But no! It is either discrete mathematics or calculus and analysis. This disparate presentation of material makes the subtle unity underlying mathematics difficult to grasp.”

“Have a heart Sol for the poor critters doing the studying. Students of Computer Science study Discrete Mathematics whereas students of Physics need continuum Mechanics and Analysis. We cannot stifle everyone with material that adds to the academic load without a commensurate return on their future professional needs.”

“You make an assumption that is not well-founded,” Sol countered. Not everything needs to be plumbed to its uttermost depths. But the fact that two canals arise from the same mathematical river must be made clear. To lose that conceptual connectivity is to impoverish education at the expense of practical utility,” Sol concluded.

Harnessed to the goal

It was only on my return flight, after much pedagogical tossing and turning, that I hit upon a neat little patch of mathematics that was both united and divided at the same time. To paraphrase Sol’s expression, a single mathematical river that fed two different canals, with few if any knowing of their common origin.

What I needed was to nail a core idea or anchor concept that would ensure that I did not stray too far afield and yet, which assured that the necessary appreciation of unity did not escape the reader. I could embellish as I felt inspired, but I should stay true to my course.

“I will choose a decent problem and solve it in a variety of ways to exhibit the richness of mathematics,” I told Sol. “I will start modestly, and perhaps a little under-ambitiously. Your idea is one that merits being worked upon time and time again to illustrate the self-consistency of mathematics. This might very well make for a series of blogs all threaded on the theme of ‘many approaches but one solution.’ I already have one example in mind. Let me work on it first,” I had replied.

“I will drive a peg in the mathematical ground using a single core idea.” I committed to Sol. “And I will show its surprising linkages to different areas of Mathematics. How it will affect young students, we will leave time to decide.”

And that is how this blog, on the derivation and proof of the Binet formula ¹ for the Fibonacci sequence ² by different methods first came to be.

We begin with some necessary preliminaries.

Sequences and Recurrence Relations

We define $ℕ = {1, 2, 3, \dots}$ as the set of natural numbers or positive integers. Throughout this blog, the sequence index $𝑛$ will belong to the set of non-negative integers: $ℕ 0 = ℕ \cup {0}$

A real-valued sequence $𝑎$ is defined as a mapping from $ℕ 0$ to the real numbers, $ℝ$ : $𝑎 : ℕ 0 \to ℝ$ To make explicit the dependence of $𝑎$ on $𝑛 \in ℕ 0$ , we may denote the sequence as $(𝑎 𝑛)$ . This notation, explicitly involving $𝑛$ , emphasizes that the sequence is an ordered list of numbers.

The defining characteristic of a sequence is its recurrence relation, explained below. You might recall two sequences from your middle or high school days [1]:

An arithmetic progression, is a sequence with an initial term, $𝑎 0$ , and a common difference $𝑑$ . The $𝑛$ ^th term of the sequence may be recursively defined as $𝑎 𝑛 = 𝑎 𝑛 - 1 + 𝑑 .$ This is also called a recurrence relation. Any term in the sequence, except for the initial term(s), may be defined by the term or terms preceding it. Not surprisingly, a recurrence relation may also be called a difference equation.
A geometric progression, is a sequence with an initial term $𝑎 0$ , and a common ratio $𝑟$ . It too may be recursively defined by the recurrence relation $𝑎 𝑛 = 𝑎 𝑛 - 1 𝑟 .$

Classification of recurrence relations

The two sequences shown above are particularly simple but also very useful. In general, a linear, constant coefficient sequence of order $𝑟$ has a recurrence relation defined as $𝑎 𝑛 = 𝑐 1 𝑎 𝑛 - 1 + 𝑐 2 𝑎 𝑛 - 2 + 𝑐 3 𝑎 𝑛 - 3 + \dots + 𝑐 𝑟 𝑎 𝑛 - 𝑟 + 𝑔 (𝑛)$ If $𝑔 (𝑛) = 0$ , the recurrence relation is called homogeneous; otherwise it is non-homogeneous.

It should now be apparent that the arithmetic and geometric progressions are both first order, linear, constant coefficient recurrence relations. The geometric progression is homogeneous. The arithmetic progression $𝑎 𝑛 = 𝑎 𝑛 - 1 + 𝑑$ is non-homogeneous as long as the common difference $𝑑 \neq 0$ . If $𝑑 = 0$ , it too is homogeneous, but such a sequence will be boring, as all the terms will be the same!

Recurrence relations and differential equations

The terminology used to classify recurrence relations is reminiscent of that used to classify differential equations. In this blog, we will restrict the scope of both recurrence relations and differential equations to homogeneous, linear, constant coefficient equations, which are shift-invariant. Their underlying unity makes studying them together both insightful and productive.

What are the similarities and differences between these two mathematical objects?

A difference equation or recurrence relation embodies shifts $𝑆$ in the value of the index $𝑛$ in the equation connecting terms of a sequence.

In a differential equation the derivative or differential operator, $𝐷$ , takes the place of the index shift when equations of functions are strung together.

Since differential equations are generally more familiar, let us first consider the equation $𝑦 (𝑥) = 𝑒 𝜆 𝑥$ . Its derivative is then $d 𝑦 d 𝑥 = 𝐷 𝑦 = 𝜆 𝑒 𝜆 𝑥 = 𝜆 𝑦 (𝑥)$ . The exponential $𝑒 𝜆 𝑥$ is said to be an eigenfunction of the differential operator $𝐷$ .³

Next, consider a sequence defined as $𝑎 𝑛 = 𝜆 𝑛$ . Its next term is denoted as $𝑆 (𝑎 𝑛) = 𝑎 𝑛 + 1 = 𝜆 𝑛 + 1 = 𝜆 (𝜆 𝑛) = 𝜆 𝑎 𝑛$ . By analogy with differential equations, we may conclude that $𝜆 𝑛$ is an eigenfunction of the shift operator $𝑆$ associated with the sequence $𝑎 𝑛$ .

We may infer that recurrence relations and differential equations are the discrete and continuous analogs of each other, with their characteristics and behaviour mirroring this fact.

The Fibonacci sequence

Let us take the Fibonacci sequence, $𝐹 : ℕ 0 \to ℕ 0$ , as a concrete example.⁴

It is a sequence in which the current term is the sum of the two preceding terms. Historically, there has been diversity in the choice of the first two numbers of the Fibonacci sequence that are needed to fire up the rest. Some started with $𝐹 0 = 0$ and $𝐹 1 = 1$ , others with $𝐹 0 = 1$ and $𝐹 1 = 1$ , whereas Fibonacci himself started with $𝐹 1 = 1$ and $𝐹 2 = 2$ . The modern mathematical convention we follow here is to start with $𝐹 0 = 0$ and $𝐹 1 = 1$ : $𝐹 0 = 0 𝐹 1 = 1 𝐹 𝑛 + 2 = 𝐹 𝑛 + 1 + 𝐹 𝑛 w i t h 𝑛 \in ℕ 0 . (1)$ This is a second order recurrence relation.

Using naive recursion on the recurrence relation to find the $𝑛$ ^th Fibonacci number is expensive in terms of time and computing resources. A formula for the $𝑛$ ^th Fibonacci number is therefore an attractive goal to work toward, and the French mathematician, Jacques Philippe Marie Binet, is credited with its discovery, although it was known to other mathematicians like Leonhard Euler, Daniel Bernoulli, and Abraham de Moivre more than a century earlier [2]. Such is the irony of history.

The shift operator $𝑆$ is defined as $𝑆 (𝐹 𝑛 ) = 𝐹 𝑛 + 1$ . Then, Equation 1 translates to the operator equation: $(𝑆 2 - 𝑆 - 𝐼) 𝐹 = 0 (2)$ where $𝐼$ is the identity operator (which leaves whatever it acts upon intact).

Now, we capitalize on the analogy between functions and sequences, between derivatives and shifts: the differential equation for $𝑦 (𝑥)$ should mirror the recurrence relation for the Fibonacci sequence.

Replacing shifts with derivatives in Equation 1, we have the following: $d 2 𝑦 d 𝑥 2 = d 𝑦 d 𝑥 + 𝑦 i . e ., d 2 𝑦 d 𝑥 2 - d 𝑦 d 𝑥 - 𝑦 = 0 . (3)$ This substitution is formal: it preserves algebraic structure but not dimensional or analytic meaning.

Using the differential operator $𝐷$ in place of the verbose $d d 𝑥$ notation, Equation 3 may be rewritten as: $(𝐷 2 - 𝐷 - 1) 𝑦 = 0 . (4)$

The recurrence relation, Equation 1, and the differential equation, Equation 3, are the discrete and continuous analogs of each other. We will revisit this idea a little later in this blog.

The Characteristic Equation

Save for a difference in symbols, Equation 2 and Equation 4 are identical in form. The common polynomial on the left may now be written as $𝑃 (𝑥)$ : $𝑃 (𝑥) = 𝑥 2 - 𝑥 - 1 = 0 (5)$ where $𝑥$ is a dummy variable with no particular significance.

Equation 5 is called the characteristic equation and it applies to both difference equations and differential equations.⁵ Its roots hold the key to solving both types of equations.

The roots of the characteristic equation, denoted here by $𝜆$ , are the solutions to the difference equation as well as the differential equation in their respective contexts.

Why is this so? As explained above in Recurrence relations and differential equations, the eigenfunctions of the differential operator are the exponentials, $𝑒 𝜆 𝑥$ .⁶ In like fashion, the eigenfunctions of the recurrence relation, or shift operator, are $𝜆 𝑛$ .

In other words, for the case of the quadratic characteristic equation with distinct roots, $𝜆 1$ and $𝜆 2$ , $𝐹 𝑛 = 𝐴 𝜆 𝑛 1 + 𝐵 𝜆 𝑛 2 a n d (6)$ and $𝑦 (𝑥) = 𝐴 𝑒 𝜆 1 𝑥 + 𝐵 𝑒 𝜆 2 𝑥 (7)$ where $𝐴$ and $𝐵$ are constants whose values satisfy the initial conditions. It is important to bear in mind that this applies when the roots of the characteristic equation are distinct.⁷

The eigenfunction is the justification. Substitution yields the verification.

Brief summary

Certain sequences lead to recurrence relations, which in turn lead to characteristic equations, whose roots, raised to integer powers, lead to closed form expressions for the general term in the sequence [3].

For certain types of differential equations, the solutions are furnished by exponentials raised to powers that are the roots of the characteristic equation.

Deriving Binet’s formula

We use Binet’s formula to independently calculate the $𝑛$ ^th term of the Fibonacci sequence for a particular $𝑛$ , without being tethered to recurrence relations. We would then have solved the puzzle of “what equation describes the terms of the Fibonacci sequence?”.

Equation 5 is the characteristic equation for the Fibonacci equation. When this quadratic is solved, we get these two roots, say $𝜑$ and $𝜓$ , so: $𝜑 = 12 [1 + \sqrt 5] a n d 𝜓 = 12 [1 - \sqrt 5] (8)$

From Equation 6, the solution for the recurrence relation is: $𝐹 𝑛 = 𝐴 𝜑 𝑛 + 𝐵 𝜓 𝑛 (9)$ We now use the two initial conditions, $𝐹 0 = 0$ and $𝐹 1 = 1$ to determine $𝐴$ and $𝐵$ . This leads to: $𝐹 0 = 0 = 𝐴 𝜑 0 + 𝐵 𝜓 0 0 = 𝐴 + 𝐵 𝐵 = - 𝐴 a n d 𝐹 1 = 1 = 𝐴 𝜑 + 𝐵 𝜓; a n d s u b s t i t u t i n g f o r 𝐵 = 𝐴 [𝜑 - 𝜓] = 𝐴 2 [(1 + \sqrt 5) - (1 - \sqrt 5)] 1 = 𝐴 \sqrt 5 𝐴 = 1 \sqrt 5 𝐵 = - 1 \sqrt 5 .$ The general term is therefore: $𝐹 𝑛 = 1 \sqrt 5 [1 + \sqrt 5 2] 𝑛 - 1 \sqrt 5 [1 - \sqrt 5 2] 𝑛 = 1 \sqrt 5 ([1 + \sqrt 5 2] 𝑛 - [1 - \sqrt 5 2] 𝑛) = 1 \sqrt 5 (𝜑 𝑛 - 𝜓 𝑛) (10)$ and this is the formula bequeathed to us by Binet [4]. It not only looks daunting, it also seems incredible. How can we get a whole number as the output from an expression involving irrational numbers like $\sqrt 5$ , unless they cancel out in some way? This suspicion must inspire us to dig a little deeper to unearth the magic.

Relationship with the number φ

The symbol $𝜑$ , used above, is reserved for a special constant that occurs widely in Nature. It is the value of an aesthetically favoured ratio, known from ancient times as the divine proportion [5] or the golden ratio.

Let a line have a length of $𝑥 + 1$ units. That particular choice of the length $𝑥$ such that $𝑥 1 = 𝑥 + 1 𝑥 g i v e s r i s e t o 𝑥 2 = 𝑥 + 1 o r e q u i v a l e n t l y 𝑥 2 - 𝑥 - 1 = 0 . (11)$

This is the same quadratic as the characteristic equation for the Fibonacci sequence.

The solution of this quadratic leads to two roots, which from the quadratic formula, are $- 𝑏 \pm \sqrt 𝑏 2 - 4 𝑎 𝑐 2 𝑎$ . Substituting $𝑎 = 1$ , $𝑏 = - 1$ and $𝑐 = - 1$ , we get the two roots to be $𝜑 = - (- 1) + \sqrt (- 1) 2 - 4 (- 1) 2 = 12 [1 + \sqrt 5] \approx 1.6180339887 (12)$ and $𝜓 = - (- 1) - \sqrt (- 1) 2 - 4 (- 1) 2 = 12 [1 - \sqrt 5] \approx - 0.6180339887 . (13)$ We also know that the sum of quadratic roots is $- 𝑏 𝑎$ and the product of the quadratic roots is $𝑐 𝑎$ . Therefore, we may assert that $𝜑 + 𝜓 = 1 ⟹ 𝜓 = 1 - 𝜑 . (14)$ Moreover, $𝜑 𝜓 = - 1 ⟹ 𝜓 = - 1 𝜑 . (15)$ Both these statements may be verified from Equations 12, 13.

The characteristic equation $𝑥 2 - 𝑥 - 1 = 0$ may also be written as $𝑥 2 = 𝑥 + 1$ , as is clear from Equation 11. This means: $𝜑 2 = 𝜑 + 1 𝜓 2 = 𝜓 + 1 . (16)$

This equivalence will come in handy later. It allows us to linearize expressions involving the roots of the characteristic equation in which a square term appears, and can lead to tractable solutions where there might otherwise be none.

We may now re-write Binet’s formula using these relations thus: $𝐹 𝑛 = 𝜑 𝑛 - 𝜓 𝑛 \sqrt 5 (17)$ $𝐹 𝑛 = 𝜑 𝑛 - (1 - 𝜑) 𝑛 \sqrt 5 (18)$ $𝐹 𝑛 = 𝜑 𝑛 - (1 - 𝜑) 𝑛 \sqrt 5 (19)$

We are now ready to tackle proving Binet’s formula by three different methods. The first method is called the Principle of Mathematical Induction, which is what we look at next.

Principle of Mathematical Induction

Proof by induction [6] is a time-honoured method of algorithmic proof, but it has one drawback: we need the formula we are setting out to prove.

But how do we get that formula in the first place? Obviously by some other method or guesswork. We have just used the characteristic equation to derive Binet’s formula; so this is of little moment to us in this blog. But it is noteworthy that this lack is the Achilles heel of proof by induction, which works well once we have a formula in hand.

Assuming that we do have a formula, proof by induction is logically clear and procedurally simple. Let us go through mathematical induction step-by-step:

We need the formula⁸ or mathematical statement we are trying to prove. It must be a function of $𝑛 \in ℕ 0$ . Let us call this formula $𝑃 (𝑛)$ .
We must first verify that $𝑃 (𝑛)$ is true for $𝑛 = 1$ or some such starting value. This is called the base case.
We then assume that $𝑃 (𝑛)$ is true for some $𝑘 \in ℕ 0$ . Why do we use $𝑘$ instead of $𝑛$ here? Because we do not want to confound a variable we use in our proof— $𝑘$ in this case—with the variable $𝑛$ in the problem statement. So, while $𝑘$ is just as arbitrary as $𝑛$ , we go out of our way to use it to differentiate it from $𝑛$ . The symbol $𝑘$ is a placeholder in the proof that disappears once the proof is complete. Think of it like a dummy variable in definite integration, for example. The assumption we make in this step—that $𝑃 (𝑘)$ is true—is called the induction hypothesis.
The next step is the meat of the method, called the induction step. In the language of mathematical logic, we need to prove that if $𝑃 (𝑘)$ is true, then $𝑃 (𝑘 + 1)$ is also true, i.e., $𝑃 (𝑘) ⟹ 𝑃 (𝑘 + 1) (20)$ where the symbol $⟹$ stands for implies. Direct evaluation of $𝑃 (𝑘 + 1)$ will usually suffice as proof in this step.

Let us recapitulate. We have verified that $𝑃 (1)$ is true in the first step. We have proved that if $𝑃 (𝑘)$ is true, then $𝑃 (𝑘 + 1)$ is also true in the third step. Substituting $𝑘 = 1$ , this means that if $𝑃 (1)$ is true, which we have verified, then $𝑃 (2)$ is also true. Substituting $𝑘 = 2$ , since we know that $𝑃 (2)$ is true, it follows that $𝑃 (3)$ is also true. And so on for all natural numbers, without end. There is an unbroken chain of logic and numbers that links the truth of the first statement or base case with the truth of all subsequent cases. This is the essence of proof by induction.

Proving Binet’s formula by induction

Let us now prove Binet’s formula by the principle of mathematical induction. To unclutter the working, we will use the version of the formula shown in Equation 17.

Since the Fibonacci recurrence involves three consecutive terms, we need two base cases to get the induction fired up. This is called strong induction. These base cases are:
1. Substituting $𝑘 = 0$ in Equation 17, we have $𝐹 0 = 1 \sqrt 5 [𝜑 0 - 𝜓 0] = 1 \sqrt 5 (1 - 1) = 0 a s r e q u i r e d .$
2. Substituting $𝑘 = 1$ in Equation 17, we have $𝐹 1 = 1 \sqrt 5 [𝜑 - 𝜓] = 1 \sqrt 5 [1 + \sqrt 5 2 - 1 - \sqrt 5 2] = 1 \sqrt 5 [1 + \sqrt 5 - 1 + \sqrt 5 2] = 1 \sqrt 5 [2 \sqrt 5 2] = 1 a s r e q u i r e d .$
Assuming that Binet’s formula holds for $𝐹 𝑘$ and $𝐹 𝑘 - 1$ , we now show that it holds for $𝐹 𝑘 + 1$ by verifying that the recurrence yields the expected form: $𝐹 𝑘 + 1 = 𝐹 𝑘 + 𝐹 𝑘 - 1 = 1 \sqrt 5 [𝜑 𝑘 - 𝜓 𝑘] + 1 \sqrt 5 [𝜑 𝑘 - 1 - 𝜓 𝑘 - 1] = 1 \sqrt 5 [𝜑 𝑘 + 𝜑 𝑘 - 1 - 𝜓 𝑘 - 𝜓 𝑘 - 1] = 1 \sqrt 5 [𝜑 𝑘 - 1 (𝜑 + 1) - 𝜓 𝑘 - 1 (𝜓 + 1)] = 1 \sqrt 5 [(𝜑 𝑘 - 1) (𝜑 2) - (𝜓 𝑘 - 1) (𝜓 2)] = 1 \sqrt 5 [𝜑 𝑘 + 1 - 𝜓 𝑘 + 1] a s r e q u i r e d . (21)$ The magic in the second last line of Equation 21 is because of Equation 16.
This completes the proof by mathematical induction. We have verified two base cases, $𝑘 = 0$ and $𝑘 = 1$ , by direct evaluation of the Binet formula. The induction step involves $𝑘 = 2$ . Since it holds for $𝑘 = 2$ , it will hold for $𝑘 = 3$ , and so on.

Just for curiosity, we could directly substitute $𝑘 = 2$ in the Binet formula to verify that it really holds, since we know from the sequence that $𝐹 2 = 1$ : $𝐹 2 = 1 \sqrt 5 [𝜑 2 - 𝜓 2] = 1 4 \sqrt 5 [(1 + \sqrt 5) 2 - (1 - \sqrt 5) 2] = 1 4 \sqrt 5 4 \sqrt 5 1 = 1 a s r e q u i r e d .$

The Generating Function

A generating function is a clothesline on which we hang up a sequence of numbers for display.
–Herbert S Wilf
generatingfunctionology [7]

The generating function [3,7] of a sequence provides a second method for deriving a formula for the $𝑛$ ^th term of the Fibonacci sequence. The characteristic equation will again pop up along the way, once again establishing its centrality to the process.⁹

We know from Equation 1 how the Fibonacci sequence may be written. Suppose we want to define a power series $𝐹 (𝑥)$ as a polynomial whose coefficients are the Fibonacci sequence—which is the generating function—we may write: $𝐹 (𝑥) = \infty \sum 𝑛 = 0 𝐹 𝑛 𝑥 𝑛 . (22)$

Because $𝐹 0 = 0$ , we may also write Equation 22—with $𝑛$ starting at $1$ rather than $0$ —as $𝐹 (𝑥) = \infty \sum 𝑛 = 1 𝐹 𝑛 𝑥 𝑛 . (23)$

Moreover, since $𝐹 1 = 1$ , we may also write Equation 23 as $𝐹 (𝑥) = 𝑥 𝐹 1 + \infty \sum 𝑛 = 2 𝐹 𝑛 𝑥 𝑛 = 𝑥 (1) + \infty \sum 𝑛 = 2 𝐹 𝑛 𝑥 𝑛 = 𝑥 + \infty \sum 𝑛 = 2 𝐹 𝑛 𝑥 𝑛 . (24)$

Using the Fibonacci recurrence, and keeping Equations 22, 23 in mind, we may write Equation 24 as $𝐹 (𝑥) = 𝑥 + \infty \sum 𝑛 = 2 (𝐹 𝑛 - 1 + 𝐹 𝑛 - 2) 𝑥 𝑛 = 𝑥 + \infty \sum 𝑛 = 2 𝐹 𝑛 - 1 𝑥 𝑛 + \infty \sum 𝑛 = 2 𝐹 𝑛 - 2 𝑥 𝑛 = 𝑥 + 𝑥 \infty \sum 𝑛 = 2 𝐹 𝑛 - 1 𝑥 𝑛 - 1 + 𝑥 2 \infty \sum 𝑛 = 2 𝐹 𝑛 - 2 𝑥 𝑛 - 2 = 𝑥 + 𝑥 \infty \sum 𝑛 = 1 𝐹 𝑛 𝑥 𝑛 + 𝑥 2 \infty \sum 𝑛 = 0 𝐹 𝑛 𝑥 𝑛 = 𝑥 + 𝑥 [𝐹 (𝑥)] + 𝑥 2 [𝐹 (𝑥)] 𝐹 (𝑥) - 𝑥 [𝐹 (𝑥)] - 𝑥 2 [𝐹 (𝑥)] = 𝑥 𝐹 (𝑥) [1 - 𝑥 - 𝑥 2] = 𝑥 𝐹 (𝑥) = 𝑥 1 - 𝑥 - 𝑥 2 . (25)$

Equation 25 is the equation of the generating function $𝐹 (𝑥)$ . Let us assign its denominator to be $𝑄 (𝑥)$ : $𝑄 (𝑥) = 1 - 𝑥 - 𝑥 2 . (26)$ Observe that $𝑄 (𝑥)$ in Equation 26 resembles the polynomial $𝑃 (𝑥)$ of the characteristic equation: Equation 5. Indeed, if the solutions of $𝑃 (𝑥) = 0$ are $𝜑$ and $𝜓$ , the solutions of $𝑄 (𝑥) = 0$ are $- 𝜑$ and $- 𝜓$ . This is shown in the graphs of these two quadratics below:

Figure 1: A comparison of the plots of the curves P(x) and Q(x). The x-axis intersections of these curves have opposite signs and are switched laterally. P(x) is the characteristic polynomial of the Fibonacci sequence. Q(x) is the denominator of the rational polynomial defining the generating function. — Figure 1: A comparison of the plots of the curves $𝑃 (𝑥)$ and $𝑄 (𝑥)$ . The $𝑥$ -axis intersections of these curves have opposite signs and are switched laterally. $𝑃 (𝑥)$ is the *characteristic polynomial* of the Fibonacci sequence. $𝑄 (𝑥)$ is the denominator of the rational polynomial defining the *generating function*.

From Figure 1, we know that the roots of $𝑄 (𝑥)$ are $- 𝜑$ and $- 𝜓$ , i.e., $𝑄 (𝑥) = 𝑘 (𝑥 - (- 𝜑)) (𝑥 - (- 𝜓)) = 𝑘 (𝑥 + 𝜑) (𝑥 + 𝜓)$ The constant $𝑘$ is necessary to ensure that we get the correct parabola out of countless ones with the same two roots. At the point $(0, 0)$ ,¹⁰ we have from the graph $𝑄 (0) = 1 = 𝑘 𝜑 𝜓 = 𝑘 (- 1)$ because $𝜑 𝜓 = - 1$ from Equation 15. Therefore, $𝑘 = - 1$ and $𝑄 (𝑥) = - (𝑥 + 𝜑) (𝑥 + 𝜓) . (27)$

So, the partial fraction expansion of $𝐹 (𝑥)$ may be written as $𝐹 (𝑥) = 𝑥 1 - 𝑥 - 𝑥 2 = 𝑥 𝑄 (𝑥) = 𝑥 - (𝑥 + 𝜑) (𝑥 + 𝜓) = 𝐴 (𝑥 + 𝜑) + 𝐵 (𝑥 + 𝜓) (28)$ It follows that $- 𝑥 = 𝐴 (𝑥 + 𝜓) + 𝐵 (𝑥 + 𝜑) (29)$

By substituting well-chosen values for $𝑥$ on both sides of Equation 29, we may reduce the solution of two simultaneous equations into the independent solution of two simple equations. We need values of $𝑥$ that set either $(𝑥 + 𝜓)$ or $(𝑥 + 𝜑)$ to zero.

If we set $𝑥 = - 𝜓$ , we get $- (- 𝜓) = 𝐵 (𝜑 - 𝜓) 𝐵 = 𝜓 𝜑 - 𝜓 = 𝜓 \sqrt 5 . (30)$

Likewise, if we set $𝑥 = - 𝜑$ , we get $- (- 𝜑) = 𝐴 (𝜓 - 𝜑) 𝐴 = 𝜑 𝜓 - 𝜑 = - 𝜑 \sqrt 5 . (31)$

Substituting into Equation 28, we get Equation 32 $𝐹 (𝑥) = 1 \sqrt 5 [𝜓 𝑥 + 𝜓 - 𝜑 𝑥 + 𝜑] (32)$ which when properly expanded will give us our generating polynomial for the Fibonacci sequence. But that is not our goal. Binet’s formula is.

Algebra versus Analysis

We now need to digress a little so that we may progress toward our goal. It requires a change in our mathematical perspective. In the context of the sum to infinity of a geometric progression or a power series like a Taylor series, we are concerned about something called the radius of convergence [1]. The equation we are looking at is: $1 1 - 𝑥 = \infty \sum 𝑘 = 0 𝑥 𝑘 = 1 + 𝑥 + 𝑥 2 + 𝑥 3 + 𝑥 4 + \dots . (33)$ where convergence occurs when $| 𝑥 | < 1$ . This statement is valid from the viewpoint of power series and analysis.

In our case, though, justification using this logic is a little slippery because convergence cannot be asserted.

So, we need an approach where the equality is claimed based on algebraic manipulation within the ring of formal power series, $[[ℝ]]$ where convergence is irrelevant but where unique inverses for series with nonzero constant term are guaranteed.

Without getting too deep into formal power series, we can look at Equation 33 as an algebraic equivalence. This means that the RHS of Equation 33 is simply another way of writing $1 1 - 𝑥$ . The $𝑥$ is called an indeterminate, rather than a variable that can take on numerical values. It is simply a symbol or placeholder in an algebraic expression.

The applicable constraint is that a formal power series $𝑓 (𝑥)$ $𝑓 (𝑥) = \infty \sum 𝑛 = 0 𝑎 𝑛 𝑥 𝑛$ has a unique reciprocal if and only if $𝑎 0 \neq 0$ [7]. This constraint is met by Equation 33 where the coefficient of $𝑥 0$ is $1$ .

If we multiply both sides of Equation 33 by $1 1 - 𝑥$ , we get $1 = (1 - 𝑥) \infty \sum 𝑘 = 0 𝑥 𝑘 . (34)$ From Equation 34 we infer that the infinite series $\infty \sum 𝑘 = 0 𝑥 𝑘$ is the multiplicative inverse or reciprocal of $(1 - 𝑥)$ . Plain long division on the LHS of Equation 33 would also lead to its RHS.

You might think that this is quibbling over trivial matters. But it is not. Operations are either meaningful and allowed, or nonsensical and disallowed, depending on strictly defined contexts. The same symbols may be used for variables and placeholders: the former can taken on numerical values; the latter are symbols that could as well have been replaced by pictographs.¹¹

Towards Binet’s formula

With that out of the way, we can work on the RHS of Equation 32. Using Equation 15 $𝜓 𝑥 + 𝜓 = 1 1 + 𝑥 𝜓; s u b s t i t u t i n g 𝜓 = - 1 𝜑 = 1 1 - 𝑥 𝜑 = \infty \sum 𝑘 = 0 (𝑥 𝜑) 𝑛) = \infty \sum 𝑘 = 0 𝜑 𝑛 𝑥 𝑛 . (35)$

Similarly, $𝜑 𝑥 + 𝜑 = 1 1 + 𝑥 𝜑; s u b s t i t u t i n g 𝜑 = - 1 𝜓 = 1 1 - 𝑥 𝜓 = \infty \sum 𝑘 = 0 (𝑥 𝜓) 𝑛 = \infty \sum 𝑘 = 0 𝜓 𝑛 𝑥 𝑛 . (36)$ Substituting into Equation 32 we get $𝐹 (𝑥) = 1 \sqrt 5 [𝜓 𝑥 + 𝜓 - 𝜑 𝑥 + 𝜑] = 1 \sqrt 5 [\infty \sum 𝑘 = 0 𝜑 𝑛 𝑥 𝑛 - \infty \sum 𝑘 = 0 𝜓 𝑛 𝑥 𝑛] = 1 \sqrt 5 \infty \sum 𝑘 = 0 [𝜑 𝑛 𝑥 𝑛 - 𝜓 𝑛 𝑥 𝑛] = \infty \sum 𝑘 = 0 1 \sqrt 5 [𝜑 𝑛 - 𝜓 𝑛] 𝑥 𝑛$

But $𝐹 (𝑥)$ was defined in Equation 22 to be $𝐹 (𝑥) = \infty \sum 𝑛 = 0 𝐹 𝑛 𝑥 𝑛 = \infty \sum 𝑘 = 0 1 \sqrt 5 [𝜑 𝑛 - 𝜓 𝑛] 𝑥 𝑛$ which, after equating coefficients of $𝑥$ gives us $𝐹 𝑛 = 𝜑 𝑛 - 𝜓 𝑛 \sqrt 5$ which is Binet’s formula as expressed in Equation 10, and we are finally done.

The Linear Algebra route

In the Fibonacci sequence, each term is defined as a linear combination of the two preceding terms. This alone should alert us to the possibility that the sequence may be constructed using linear algebra and matrices. And we would not be wrong.

Indeed, Strang [9, pp 340–341], derives the Binet formula from first principles using only the Fibonacci recurrence relation, Equation 1.

I will largely mirror Strang’s development to demonstrate the third way in which Binet’s formula may be derived. Whether or not “all roads literally lead to Rome today”, all derivations lead to the same formula of Binet.

Vectorizing the recurrence formula

The equation $𝐹 𝑛 + 2 = 𝐹 𝑛 + 1 + 𝐹 𝑛$ is a scalar expression which has two input terms on its RHS, and one output term on its LHS. How may we recast this expression using vectors and matrices?

We may write $𝐹 𝑛 + 2 = [11] [𝐹 𝑛 + 1 𝐹 𝑛]$ but apart from complicating the notation, it yields us little by way of economy, efficiency, or insight. It appears contrived simply to accommodate vector-matrix notation. We need to dig deeper.

We could start by defining a two-dimensional vector for the two input terms so: $𝐮 𝑛 = [𝐹 𝑛 + 1 𝐹 𝑛] (37)$ in which case, the vector for the output should be: $𝐮 𝑛 + 1 = [𝐹 𝑛 + 2 𝐹 𝑛 + 1] (38)$

Note that because $𝐹 𝑛 + 1$ is part of the input, its value is already known. The only missing ingredient is the matrix $𝐴$ to give us the vector-matrix equation $𝐮 𝑛 + 1 = 𝐴 𝐮 𝑛 (39)$ Let us formally solve for $𝐴$ by setting it to be $𝐴 = [𝑎 𝑏 𝑐 𝑑] (40)$ We then have $𝐹 𝑛 + 2 = 𝑎 𝐹 𝑛 + 1 + 𝑏 𝐹 𝑛 = 𝐹 𝑛 + 1 + 𝐹 𝑛$ giving $𝑎 = 1$ and $𝑏 = 1$ . But what about the second term? Note that the second component of the output is by definition $𝐹 𝑛 + 1$ . So, the second equation is $𝐹 𝑛 + 1 = 𝑐 𝐹 𝑛 + 1 + 𝑑 𝐹 𝑛$ giving us $𝑐 = 1$ and $𝑑 = 0$ . The matrix $𝐴$ is therefore $𝐴 = [1110] (41)$ and we have now vectorized the Fibonacci recurrence relation.

Let us recapitulate for a moment. The input is naturally a two-dimensional vector, $𝐮 𝑛$ . To accommodate the vector framework, we have deliberately cast the output as a two-dimensional vector as well: $𝐮 𝑛 + 1$ , whose first component is $𝐹 𝑛 + 2$ and second component is $𝐹 𝑛 + 1$ . This notation is consistent with the definition for the vector $𝐮 𝑛 + 1$ .

But what is $𝐹 𝑛 + 1$ on the LHS? Have we introduced something extraneous? Why, it is an input on the RHS in Equation 37, and therefore comes already defined. We have not introduced any extraneous relationships into the original recurrence equation.

By introducing $𝐹 𝑛 + 1$ not only as a given input variable, but also as part of the output, we have vectorized the Fibonacci recurrence. This leap of the imagination—where both input and output are two dimensional vectors—is key to reformulating the Fibonacci recurrence as a matrix equation. This point might be glibly glossed over, but the change in perspective it entails is vital to vectorizing the equation as shown in Equation 39.

The initial conditions are $𝐮 0 = [10]; 𝐮 1 = [11] . (42)$

Obtaining the eigenvalues

Each term of the Fibonacci recurrence is the result of pre-multiplying the previous term by $𝐴$ . Therefore, the $𝑛$ ^th term is given by $𝐮 𝑛 = 𝐴 𝑛 𝐮 0 . (43)$

To enable efficient evaluation of $𝐴 𝑛$ , we need to diagonalize $𝐴$ . For that we need the eigenvalues of $𝐴$ , which are the roots of the characteristic polynomial of $𝐴$ , given by $d e t (𝐴 - 𝜆 𝐼) = 0 .$

The algorithm is as follows:

The $2 \times 2$ identity matrix is given by $𝐼 = [1001]$
The matrix $(𝐴 - 𝜆 𝐼)$ is $𝐴 - 𝜆 𝐼 = [1 - 𝜆 1 1 - 𝜆] .$
The characteristic polynomial is given by $d e t (𝐴 - 𝜆 𝐼) = (1 - 𝜆) (- 𝜆) - 1 = 𝜆 2 - 𝜆 - 1 = 0 .$ But this polynomial is just $𝑃 (𝜆)$ in Equation 5. From Equation 8, we know the roots of this polynomial to be $𝜑$ and $𝜓$ .

It is interesting to note that in both instances, this polynomial is called the characteristic polynomial, although it has arisen in different mathematical contexts. Even more interesting, it is the same polynomial.

Determining the eigenvectors

We know that the eigenvalues of $𝐴$ are $𝜑$ and $𝜓$ as defined in Equation 8. Let $𝐞 𝜑 = [𝑎 𝑏]$ be the eigenvector corresponding to the eigenvalue $𝜑$ . Then, because $(𝐴 - 𝜑 𝐼) 𝐞 𝜑 = 𝟎,$ we have: $[1 - 𝜑 1 1 - 𝜑] [𝑎 𝑏] = [00] .$ The two equations arising from this are: $(1 - 𝜑) 𝑎 + 𝑏 = 0 𝑎 - 𝜑 𝑏 = 0 .$ The second equation shows that $𝑎$ and $𝑏$ are linearly dependent, i.e., we may freely choose the value of $𝑏$ for our convenience, and that will determine the value of $𝑎$ . In this case, we choose $𝑏 = 1$ and that gives us $𝑎 = 𝜑$ . Therefore, one eigenvector is $𝐮 𝜑 = [𝜑 1] . (44)$

Likewise, the other eigenvector is $𝐮 𝜓 = [𝜓 1] . (45)$

Diagonalizing the matrix A

In my blog Eigenvalues and Eigenvectors—Why are they important? I have explained how to diagonalize a square matrix with distinct eigenvalues, as in the present case. I will use the notation from that blog, except that the matrix $𝑀$ there is now our matrix $𝐴$ here.

The algorithm is:

The matrix $𝑃$ has columns that are the eigenvectors, i.e., $𝑃 = [𝜑 𝜓 11] .$
The inverse of $𝑃$ , denoted by $𝑃 - 1$ , is [10] $𝑃 - 1 = 1 𝜑 - 𝜓 [1 - 𝜓 - 1 𝜑] .$
The diagonal matrix $𝐷$ is the one whose diagonal entries are the eigenvalues. In our case, this is $𝐷 = [𝜑 0 0 𝜓] .$
We assert that¹² $𝐴 = 𝑃 𝐷 𝑃 - 1 𝐴 𝑛 = 𝑃 𝐷 𝑛 𝑃 - 1$
Recall from Equation 43 that $𝐮 𝑛 = 𝐴 𝑛 𝐮 0 = 𝑃 𝐷 𝑛 𝑃 - 1 𝐮 0 = 1 𝜑 - 𝜓 [𝜑 𝜓 11] [𝜑 𝑛 0 0 𝜓 𝑛] [1 - 𝜓 - 1 𝜑] [10] = 1 𝜑 - 𝜓 [𝜑 𝑛 + 1 𝜓 𝑛 + 1 𝜑 𝑛 𝜓 𝑛] [1 - 𝜓 - 1 𝜑] [10] = 1 𝜑 - 𝜓 [𝜑 𝑛 + 1 - 𝜓 𝑛 + 1 - 𝜑 𝑛 + 1 𝜓 + 𝜓 𝑛 + 1 𝜑 𝜑 𝑛 - 𝜓 𝑛 - 𝜓 𝜑 𝑛 + 𝜑 𝑛 𝜓] [10] = 1 𝜑 - 𝜓 [𝜑 𝑛 + 1 - 𝜓 𝑛 + 1 𝜑 𝑛 - 𝜓 𝑛] = [𝐹 𝑛 + 1 𝐹 𝑛] . (46)$
The last line in Equation 46 comes from the definition of $𝐮 𝑛$ in Equation 37. Equating components, $𝐹 𝑛 = 1 𝜑 - 𝜓 [𝜑 𝑛 - 𝜓 𝑛] = 1 \sqrt 5 [𝜑 𝑛 - 𝜓 𝑛]$ which is again Binet’s formula as stated in Equation 10, derived this time using linear algebra.
The matrix $𝐴$ when raised to the $𝑛$ ^th power actually embodies the $𝑛$ ^th and surrounding terms of Fibonacci sequence in its very entries. This will be discussed further in the section The Companion Matrix below.

This entire method generalizes naturally to any linear recurrence with constant coefficients.

Points to Ponder

It has been a long and arduous trek to get here. The wonder is that although the routes we took were mathematically different, the destination that we reached has been the same in all three cases. This is because the edifice of mathematics is logically consistent and unshakably strong. It is built to endure.

In this section, I have penned the thoughts that occurred to me while I was writing this blog. When computing Fibonacci numbers—especially using Binet’s formula—we need to bear in mind a few computational considerations.

For example, because of the $\sqrt 5$ in Binet’s formula, when we compute it programmatically, we are forced to use floating point arithmetic, which does not output integers. We must use a rounding function to get the Fibonacci integers correctly.

Approximation

Binet’s formula holds within itself a rough and ready approximation of the $𝑛$ ^th Fibonacci number. Of the two numbers in the Binet formula, $| 𝜑 | > 1$ , whereas $| 𝜓 | < 1$ . The question then naturally arises, “When may we ignore the second term?”, whose absolute value is $| | | | | 𝜓 𝑛 \sqrt 5 | | | | | .$ The greatest value of the above expression is when $𝑛 = 0$ when it equals $1 \sqrt 5 \approx 0.44721$ which is less than $0.5$ . Therefore, we may drop the second term for all values of $𝑛$ .¹³

Accordingly, we may use $𝐹 𝑛 \approx r o u n d [𝜑 𝑛 \sqrt 5] = r o u n d [1 \sqrt 5 [1 + \sqrt 5] 𝑛] (47)$ for all values of $𝑛$ . Note that $r o u n d$ stands for the rounding function.

Precision and accuracy

When a computer program is written in any language there are several constraints to bear in mind:

Total memory available on the machine;
The size of the largest integers or floats that are supported in that language; and
Whether floats are used instead of integers, because their representation in binary is not always exact.

While Binet’s formula is a time-saver, it is not particularly suited to computational accuracy. The reason is the appearance of the irrational number $\sqrt 5$ in Binet’s formula which forces any program implementing it to use floats. For example, a standard double precision provides about 15 decimal digits of precision.

Estimating the limits of precision is a little tricky because it is dependent on the machine, the programming language, and its implementation. The limits will occur in the vicinity of the Fibonacci numbers that are fifteen digits long. We estimate the number $𝑛$ associated with the limits of precision by requiring: $𝐹 𝑛 \approx 1015 \approx 𝜑 𝑛 \sqrt (5); t a k i n g l o g a r i t h m s 𝑛 \approx l o g 10 (1015) + l o g 10 (\sqrt 5) l o g 10 (𝜑) \approx 73.447 (48)$

The Fibonacci numbers having fifteen digits are for values of $𝑛 \in {69, 70, 71, 72, 73}$ [11,12]. We therefore expect computational errors to start manifesting from numbers in the above set. Note that our calculated value of $𝑛 = 73$ occurs at the high end of this band. Observe also that for $𝑛 \geq 74$ , the Fibonacci numbers are 16 or more digits long, as demonstrated in the tabulation below.

The Julia script recur-binet-seventy.jl illustrates the onset of rounding errors in my computer implementation:

n	Recurrence	Binet	Approximate Binet
`69`	`117669030460994`	`117669030460994`	`117669030460994`
`70`	`190392490709135`	`190392490709135`	`190392490709135`
`71`	`308061521170129`	`308061521170130`	`308061521170130`
`72`	`498454011879264`	`498454011879265`	`498454011879265`
`73`	`806515533049393`	`806515533049395`	`806515533049395`
`74`	`1304969544928657`	`1304969544928660`	`1304969544928660`
`75`	`2111485077978050`	`2111485077978055`	`2111485077978055`

The Fibonacci number $𝐹 71$ has 15 digits: 308,061,521,170,129 and the errors start manifesting at $𝑛 = 71$ as shown above. We were in the right ball park as far as the estimation in Equation 48 is concerned.

Note that the values put out by the approximation in Equation 47 and the full Binet formula are identical in the above table.

But what is the remedy for the slippage in accuracy?

We resort to the types BigInt and BigFloat provided by Julia with a configurable precision in bits. The code is available in the file recur-binet-comp-big.jl. The output from this file confirms that the first one huncred Fibonacci numbers are the same whether computed by the recurrence formula or by the Binet formula. We have thus overcome the limitations in precision and accuracy, at least for the first one hundred Fibonacci numbers.

The Companion Matrix

There is, in addition, a sneaky method by which we may implement the recurrence formula using matrices: it is solely integer-based and does not suffer from floating point rounding errors. And it may be optimized for speed.

The matrix $𝐴$ is called the companion matrix for the Fibonacci sequence [13]: $𝐮 𝑛 = 𝐴 𝑛 𝐮 0 [𝐹 𝑛 + 1 𝐹 𝑛] = [1110] 𝑛 [10] (49)$ Surely, the powers of the matrix $𝐴$ must encode the Fibonacci numbers within themselves in order to generate the entire sequence as $𝑛$ is varied. We tabulate below five values of $𝑛$ for which the matrix $𝐴 𝑛$ has been evaluated. $𝐴 1 = [1110] 𝐴 2 = [2111] 𝐴 3 = [3221] 𝐴 4 = [5332] 𝐴 5 = [8553]$ The pattern that emerges leads us to infer that $𝐴 𝑛 = [𝐹 𝑛 + 1 𝐹 𝑛 𝐹 𝑛 𝐹 𝑛 - 1] (50)$ which may be proved by induction, by harking back to Equation 1.

So, the matrix $𝐴 𝑛$ gives us three values for each exponentiation. The new value $𝐹 𝑛 + 1$ is the matrix entry at the first row and column at the top left hand corner, conventionally referred to as $𝑎 11$ .

If we can raise the integer-valued matrix $𝐴$ to the $𝑛$ ^th power, we will have at our fingertips a method to compute the $𝑛$ ^th Fibonacci number on demand, bypassing inaccuracies arising from floating point arithmetic.

A Julia script to do just that is available as fibonacci-matrix.jl, and it has been used to compute the first one hundred Fibonacci numbers correctly, thanks to integer arithmetic and fast matrix algorithms.

The perceptive among you might have realized that we are really using the original definition of Equation 1 here, and you would be correct. This method is attractive simply because linear algebra has spawned many efficient algorithms that make matrix computations fast and reliable in comparison to naive recursion using the original recurrence relation.

Integers from irrationals?

The Fibonacci sequence is composed entirely of integers, whereas Binet’s formula embodies the irrational number $\sqrt 5$ as its centrepiece. How is this possible? How can a discrete recurrence relation formula involving only integers have a closed-form solution involving irrational numbers? Is there any guarantee that we will not get an irrational Fibonacci number?

The answer is a resounding “Yes!”. There are three ways to look at this, outlined below.

Recurrence Relation

The defining recurrence relation itself, Equation 1, enforces each Fibonacci number to the be the sum of the preceding two integers. Because addition among the integers is a closed operation, the result is also guaranteed to be an integer.

Exponentiating the Companion Matrix

The top left entry of $𝐴 𝑛$ is the value of $𝐹 𝑛 + 2$ . Since Matrix $𝐴$ starts out as shown in Equation 41 and since its entries are composed of multiplications and additions of integers which are closed for the integers, we again have a guarantee of integer-valued Fibonacci numbers.

Algebra of the Binet formula

While the above arguments are solid, the presence of $\sqrt 5$ in Binet’s formula does give rise to room for doubt. Let us backtrack a bit to better understand Binet’s formula from the standpoint of abstract algebra, albeit without too much jargon. Note that the unnumbered equations below have all been encountered before; only the new ones are numbered.

In its literal form, Binet’s formula, Equation 10, is: $𝐹 𝑛 = 1 \sqrt 5 ([1 + \sqrt 5 2] 𝑛 - [1 - \sqrt 5 2] 𝑛) .$ This is purely a sum, quotient, and exponentiation of numbers that needs to be evaluated for any given $𝑛 \in ℕ 𝟘$ . The only variable is the exponent $𝑛$ . Also, note the generous presence of the irrational number $\sqrt 5$ in the numerator and denominator of the expression. Our goal is to prove to ourselves, unlikely though it might seem, that this expression will always evaluate to an integer.
The first step is to make the substitutions $𝜑 = 1 + \sqrt 5 2 𝜓 = 1 - \sqrt 5 2 .$ Binet’s formula may now be written as $𝐹 𝑛 = 𝜑 𝑛 - 𝜓 𝑛 \sqrt 5 .$
The second step is to observe that $(𝜑 - 𝜓) = \sqrt 5$ . If we substitute $\sqrt 5$ with this expression, we end up with [14]: $𝐹 𝑛 = [𝜑 𝑛 - 𝜓 𝑛 𝜑 - 𝜓] . (51)$
We are used to replacing symbols with numbers when evaluating formulae. But why would we proceed in the opposite direction and replace perfectly clear numbers with symbols? This change of viewpoint converts a purely numerical exercise into fodder for abstract algebra. To appreciate the logic, we need to digress a little to review the idea of a polynomial.
In high school and early university, we have known polynomials as expressions containing variables that can be used to solve equations and graph functions. Untethering polynomials from these tasks frees us to view and study them as mathematical objects in their own right. And the insights therefrom are rewarding.
In abstract algebra, a polynomial represents a structure in which two elements—the coefficients and the something else—are multiplied together and summed. This generic polynomial may be defined as $𝑟 ≜ 𝑟 𝑛 𝑡 𝑛 + 𝑟 𝑛 - 1 𝑡 𝑛 - 1 + \dots + 𝑟 1 𝑡 + 𝑟 0$ where $𝑟 0 \dots 𝑟 𝑛 \in ℂ$ and $𝑛 \in ℕ 𝟘$ while $𝑡$ is undefined [15]. We call $𝑡$ an indeterminate.
Why such a contrived definition? To facilitate a deeper study of the polynomial bereft of its utilitarian underpinnings. The polynomial is simply a sum of products where one of the multiplicands is a complex number.¹⁴ The other multiplicand may be generalized. The set of polynomials so defined forms what is known as a ring of polynomials, $ℂ [𝑡]$ . [15].
How did we get $𝜑$ and $𝜓$ ? They are the two distinct roots to the equation $𝑃 (𝑥) = 𝑥 2 - 𝑥 - 1 = 0$ , which is a non-zero polynomial having only integer coefficients. Because the coefficient of its highest degree term—also called the leading coefficient—is one, $𝑃 (𝑥)$ is called a monic polynomial.
Now, for any quadratic equation $𝑎 𝑥 2 + 𝑏 𝑥 + 𝑐 = 0$ , with roots $𝛼$ and $𝛽$ , we know that the sum of the roots $(𝛼 + 𝛽) = - 𝑏 𝑎$ and the product of the roots, $(𝛼 𝛽) = 𝑐 𝑎$ . In our case, the roots of $𝑃 (𝑥) = 0$ are the numbers $𝜑$ and $𝜓$ . Note that because the coefficients of $𝑃 (𝑥)$ are known—even if we do not know the values of $𝜑$ and $𝜓$ —we do know the sum and the product of the roots as: $𝜑 + 𝜓 = - (- 1) 1 = 1 𝜑 𝜓 = - 1 1 = - 1 .$ This is something quite powerful, even if under-recognized. The known coefficients of the polynomial tell us something about the unknown roots even before the equation is solved.
When we do solve for $𝑃 (𝑥)$ , as already known, we get two distinct roots $𝜑 = 1 + \sqrt 5 2 𝜓 = 1 - \sqrt 5 2$ Although these roots of $𝑃 (𝑥) = 0$ embody the irrational number $\sqrt 5$ , they are called, believe it or not, algebraic integers because $𝑃 (𝑥)$ is a monic polynomial with integer coefficients.
We have now converted the Binet formula from a number needing to be evaluated into a ratio of polynomials in $𝜑$ and $𝜓$ , even though they are both numbers themselves rather than variables. In any other context, if we had talked of a polynomial where the “variables” are numbers, it would have been laughable. But the vantage of abstract algebra allows us to do this to better understand the algebraic structure of the expression. We can now view $𝐹 𝑛$ as a polynomial in two indeterminates [15]
Let $𝑁 (𝜑, 𝜓) = 𝜑 𝑛 - 𝜓 𝑛$ and $𝐷 (𝜑, 𝜓) = 𝜑 - 𝜓$ be the numerator and denominator polynomials in Binet’s formula. If we interchanged $𝜑$ and $𝜓$ in each of them, we will get the negative of the original: $𝑁 (𝜑, 𝜓) = 𝜑 𝑛 - 𝜓 𝑛 𝑁 (𝜓, 𝜑) = 𝜓 𝑛 - 𝜑 𝑛 = - (𝜑 𝑛 - 𝜓 𝑛) = - 𝑁 (𝜑, 𝜓) 𝐷 (𝜑, 𝜓) = 𝜑 - 𝜓 𝐷 (𝜓, 𝜑) = 𝜓 - 𝜑 = - (𝜑 - 𝜓) = - 𝐷 (𝜑, 𝜓) .$ Because of this change in sign, both $𝑁 (𝜑, 𝜓)$ and $𝐷 (𝜑, 𝜓)$ are called alternating or anti-symmetric polynomials. But when we take their quotient, the two changes of sign in the numerator and denominator, cancel out and the result is a symmetric polynomial: $𝑓 (𝜑, 𝜓) = 𝑁 (𝜑, 𝜓) 𝐷 (𝜑, 𝜓) = [𝜑 𝑛 - 𝜓 𝑛 𝜑 - 𝜓] = 𝑁 (𝜓, 𝜑) 𝐷 (𝜓, 𝜑) = [𝜓 𝑛 - 𝜑 𝑛 𝜓 - 𝜑] = 𝑓 (𝜓, 𝜑) .$
As written in Equation 51, Binet’s formula is now a quotient of polynomials which, taken as a whole, is symmetric, not in some unknown variables, but in the known algebraic integers $𝜑$ and $𝜓$ as “indeterminates”. We may re-verify this symmetry by interchanging $𝜑$ and $𝜓$ to get the original polynomial again, by multiplying both numerator and denominator by $(- 1 - 1)$ : $𝑓 (𝜑, 𝜓) = [𝜑 𝑛 - 𝜓 𝑛 𝜑 - 𝜓]; m u l t i p l y b y (- 1 - 1) = [- 1 (𝜑 𝑛 - 𝜓 𝑛) - 1 (𝜑 - 𝜓)] = [𝜓 𝑛 - 𝜑 𝑛 𝜓 - 𝜑] = 𝑓 (𝜓, 𝜑) .$
Binet’s formula is a symmetric, polynomial of degree $𝑛 - 1$ , with integer coefficients, in two algebraic integers, $𝜑$ and $𝜓$ as the “indeterminates”.
Why do we need $𝑃 (𝑥)$ to be a monic polynomial? And what is so special about it? Because only for monic polynomials with $𝑎 = 1$ do the sums and products of roots equal simple integer coefficients, rather than rational numbers. Hark back to the sum and product of the roots. The generic quadratic $𝑎 𝑥 2 + 𝑏 𝑥 + 𝑐 = 0$ becomes monic when $𝑎 = 1$ . And the sum and product of its roots become $𝜑 + 𝜓 = - 𝑏 𝑎 = - 𝑏 1 = - 𝑏 𝜑 𝜓 = 𝑐 𝑎 = 𝑐 1 = 𝑐 . (52)$ The sum and product of its roots are simply the signed coefficients of $𝑃 (𝑥)$ , which are integers.
Why do we need a symmetric polynomial in $𝑓 (𝜑, 𝜓)$ ? The fundamental theorem of symmetric polynomials [15,16] states that every symmetric polynomial may be expressed as a linear sum of elementary symmetric polynomials.
And, pray, what are these latter mathematical objects? For $𝜑$ and $𝜓$ they are the sum and product of these two: $(𝜑 + 𝜓)$ , and $(𝜑 𝜓)$ . The expression $𝜑 𝑛 - 𝜓 𝑛 𝜑 - 𝜓$ —which is a symmetric polynomial in $𝜑$ and $𝜓$ , with integer coefficients—can be expressed as a polynomial in the elementary symmetric polynomials $(𝜑 + 𝜓)$ and $(𝜑 𝜓)$ with integer coefficients.
Because $(𝜑 + 𝜓) = 1$ and $(𝜑 𝜓) = - 1$ , the symmetric polynomial representing the Binet formula, when expressed in terms of elementary symmetric polynomials, evaluates to an integer.
There is an additional, clean way of demonstrating this using long division. The quotient in Equation 51 may be shown to be exact, without remainder, and a symmetrical polynomial itself: $(𝜑 𝑛 - 𝜓 𝑛) = (𝜑 - 𝜓) (𝜑 𝑛 - 1 𝜓 0 + 𝜑 𝑛 - 2 𝜓 + \dots + 𝜑 1 𝜓 𝑛 - 2 + 𝜑 0 𝜓 𝑛 - 1) i . e ., 𝜑 𝑛 - 𝜓 𝑛 𝜑 - 𝜓 = 𝑛 - 1 \sum 𝑘 = 0 𝜑 𝑛 - 1 - 𝑘 𝜓 𝑘 .$ Mere inspection will reveal this as a symmetric polynomial and there is no remainder. The quotient is expressible as a linear sum of the elementary symmetric polynomials $(𝜑 + 𝜓) = 1$ and $(𝜑 𝜓) = - 1$ , and will therefore be an integer itself.
Whew! We have at long last demonstrated that the formula of Binet does give us integers for all $𝑛$ .

Comment on polynomial long division

It is striking that polynomial long division has been featured twice in our mathematical journey. Once, it was used in the context of formal power series to obtain a generating function. The second time, it was used in the ring of symmetric polynomials to assert the integral value of the Binet formula. In both cases, it has aided in prising open results that would otherwise have been more tedious to obtain.

Centrality of the characteristic equation.

The polynomials $𝑃 (𝑥)$ , $𝑄 (𝑥)$ and the numbers $𝜑$ and $𝜓$ pop up along the way regardless of our approach to obtaining a closed form solution to the Fibonacci recurrence relation. These objects are, in a manner of speaking, embedded in the structure of Fibonacci sequence and they show up whenever we start digging into it. They are central to it.

Continuous function version

Is there a continuous function, whose values at integers give us the Fibonacci sequence? In such a case, the Fibonacci sequence will be a discretely-sampled version of that function. This tempting thought occurred to me as I was writing this blog.

When the Fibonacci numbers are shown as data points and plotted with piecewise linear interpolation by Gnuplot, we get an impressive curve connecting the values of the Fibonacci sequence. It is shown in Figure 2. The downside is that we do not have analytic function to describe this curve.

Figure 2: Plot of the first twenty-one Fibonacci numbers as filled circles. The line connecting the points is a piecewise linear interpolation provided by Gnuplot. Unfortunately, it does not have a closed form expression. See the text for a discussion on why an exact continuous analog of the sequence is fraught with complications. — Figure 2: Plot of the first twenty-one Fibonacci numbers as filled circles. The line connecting the points is a piecewise linear interpolation provided by `Gnuplot`. Unfortunately, it does not have a closed form expression. See the text for a discussion on why an exact continuous analog of the sequence is fraught with complications.

But is there a better way? Yes, but it is not trivial.

In the section Recurrence relations and differential equations earlier in this blog, we explored the analogy between recurrence relations and differential equations and their respective “eigenfunctions”: $𝜆 𝑛$ and $𝑒 𝜆 𝑥$ . However, we cannot assert that one is the continuous version of the other simply because: $1.618 \approx 𝜑 \neq 𝑒 𝜑 \approx 5.043; t h e r e f o r e 𝜑 𝑛 \neq 𝑒 𝜑 𝑛 a n d - 0.618 \approx 𝜓 \neq 𝑒 𝜓 \approx 0.539; t h e r e f o r e 𝜓 𝑛 \neq 𝑒 𝜓 𝑛 . (53)$

The logical way forward is to define a continuous-valued function based on the Binet formula. But such a function does not have a standard name or symbol. Nevertheless, it is sensible to christen it the Binet-Fibonacci function $𝐹 (𝑥) f o r 𝑥 \in ℝ$ and define it so: $𝐹 (𝑥) = 𝜑 𝑥 - 𝜓 𝑥 \sqrt 5 = 𝑒 𝑥 l n 𝜑 - 𝑒 𝑥 l n 𝜓 \sqrt 5 s o t h a t 𝐹 (𝑛) = 𝜑 𝑛 - 𝜓 𝑛 \sqrt 5 = 𝑒 𝑛 l n 𝜑 - 𝑒 𝑛 l n 𝜓 \sqrt 5 = 𝐹 𝑛 . (54)$ We get the Fibonacci sequence by substituting $𝑥 = 𝑛$ as shown in Equation 54.

However, because $𝜓$ is negative and the logarithm of a negative number is complex,¹⁵ $𝐹 (𝑥)$ is a complex-valued function. But when $𝑥 = 𝑛$ , $𝐹 (𝑛)$ assumes only real values and we get the Fibonacci sequence. When $𝑥$ is not an integer, we can and do get an imaginary part as well.

There is no complication with $𝜑 𝑥$ because it is a positive real number raised to a real power, whose value will be real. The kid gloves must be put on only for $𝜓 𝑥$ because $𝜓$ is a negative real number that is ideally expressed using the polar form of a complex number before being exponentiated. $𝜓 = - | 𝜓 | = | 𝜓 | (- 1) = | 𝜓 | 𝑒 𝑖 𝜋 𝜓 𝑥 = | 𝜓 | 𝑥 𝑒 𝑖 𝜋 𝑥 (55)$

The real part of $𝐹 (𝑥)$ symbolized by $𝐹 ℜ (𝑥)$ connects all the Fibonacci numbers in a perfectly smooth curve as shown in Figure 3. Its equation is: $𝐹 ℜ (𝑥) = [𝜑 𝑥 - 𝜓 𝑥 \sqrt 5] = [𝜑 𝑥 - | 𝜓 | 𝑥 c o s (𝜋 𝑥) \sqrt 5] (56)$

Likewise, the imaginary part of $𝐹 (𝑥)$ is denoted by $𝐹 ℑ (𝑥)$ : $𝐹 ℑ (𝑥) = [𝜑 𝑥 - 𝜓 𝑥 \sqrt 5] = [- | 𝜓 | 𝑥 s i n (𝜋 𝑥) \sqrt 5] (57)$

It is now easy to verify that the imaginary part vanishes at integer values of $𝑛$ because $s i n (𝜋 𝑛) = 0$ for every integer $𝑛$ . Thus $𝐹 ℑ (𝑥) = - | 𝜓 | 𝑛 s i n (𝜋 𝑛) \sqrt 5 = 0$ . Equivalently, for integer $𝑛$ , we have $𝜓 𝑛 = (- 1) 𝑛 | 𝜓 |$ , which is real. So $𝜓 𝑛$ is real and hence $𝐹 (𝑛)$ is real.

This interesting derivation shows that although $𝐹 (𝑥)$ is a complex-valued function modelling the Binet formula for continuous $𝑥$ , its values at $𝑥 = 𝑛$ are not only real, but also integers. Does that astound you? It still takes my breath away, every time I ponder it. We will now plot the real and imaginary parts of this function $𝐹 (𝑥)$ .

Figure 3: Graph of the real part, F_{\Re}(x), of the continuous function F(x) modelled on Binet’s formula. The filled circles are the values of the Fibonacci sequence at integer values of x. See the box in Figure 2 for the values. — Figure 3: Graph of the real part, $𝐹 ℜ (𝑥)$ , of the continuous function $𝐹 (𝑥)$ modelled on Binet’s formula. The filled circles are the values of the Fibonacci sequence at integer values of $𝑥$ . See the box in Figure 2 for the values.

Figure 4: Graph of the imaginary part, F_{\Im}(x), of the continuous function F(x) modelled on Binet’s formula. The filled circles are the values at integers and are all zero, demonstrating that the Fibonacci sequence is a real one. — Figure 4: Graph of the imaginary part, $𝐹 ℑ (𝑥)$ , of the continuous function $𝐹 (𝑥)$ modelled on Binet’s formula. The filled circles are the values at integers and are all zero, demonstrating that the Fibonacci sequence is a real one.

Key Takeaways

The Fibonacci Equation 1 is a second order, linear, constant coefficient, homogeneous recurrence relation. These attributes are similar to those of second order, linear, constant coefficient, homogeneous differential equations. Both share the characteristic equation as a gateway to their solution.

The numbers $𝜑$ , the golden ratio, and its negative reciprocal, $𝜓$ , arising as the two solutions to the polynomial $𝑥 2 - 𝑥 - 1 = 0$ have distinctive properties that account for the behaviour of the Fibonacci sequence. Like $𝜋$ and $𝑒$ they are irrational numbers. Unlike them, though, they are algebraic integers and algebraic numbers. Their sum, $𝜑 + 𝜓 = 1$ . Their product $𝜑 𝜓 = - 1$ .

Binet’s formula solves the Fibonacci recurrence and, in this blog, it is derived and proved using:

mathematical induction;
generating functions; and
linear algebra.

The interlocking structural integrity of mathematics is thereby demonstrated because all three approaches lead to the same formula of Binet.

Because the irrational number $\sqrt 5$ occupies a central place in the formula, one might wonder how it could lead to the integer-valued Fibonacci sequence. We have outlined reasons why this is so, without going too much into the detailed abstract algebra that assures it.

The curve $𝐹 ℜ (𝑥)$ , representing the real part of $𝐹 (𝑥))$ , is wondrous in that it is integer-valued at the integers, i.e., for $𝑛 \in ℕ 0, 𝐹 ℜ (𝑛) \in ℕ 0$ . This means that $𝐹 (𝑛)$ is an integer to integer mapping, which is exactly what an integer-valued sequence—like the Fibonacci sequence—really is.

Even more interesting is that at integers $𝑛$ , the imaginary part of $𝐹 (𝑥)$ , becomes zero, i.e., $𝐹 ℑ (𝑛) = 0$ . Therefore, $𝐹 ℜ (𝑥)$ is the exact, continuous, real-valued function that connects the data points of the Fibonacci sequence, even if $𝐹 (𝑥)$ is complex-valued when the variable is not an integer.

If these—and possibly other—properties cause astonishment in you, welcome to the club! The mansion of Mathematics holds within itself countless such treasures.

Websites worth visiting

The Fibonacci numbers hold within themselves an endless fascination. I will likely blog about them again in the future. Meanwhile, I have collated here some links to websites that expound on the properties of the Fibonacci numbers.

Dr Ron Knott, a mathematician affiliated with the University of Surrey, has probably the most exhaustive website dedicated to the Fibonacci numbers [17]. Definitely a site that should be browsed.
Another interesting mathematical website that should be visited is Alexander Bogomolny’s Cut the Knot website [18]. Not only does it show how the Binet formula may be derived from generating functions, it contains a wealth of insights on many other mathematical topics.
The Fibonacci Quarterly [19] is a serious journal on matters Fibonacci that has been published since 1963. This shows the evergreen interest on the Fibonacci numbers and their impact on many aspects of Nature and life in general.
Phil Nowell’s blog [20] shows how to derive the $𝑛$ ^th term of the Fibonacci sequence using linear algebra, as we have done above in the section The Linear Algebra route.
For a discussion on the accuracy and efficiency of computing the Binet formula, see this blog by Robin Houston [21].
A multiplicity of helpful viewpoints and answers is contained in this Mathematics StackExchange question [22]. It is an example of how interactions on the Web may be helpful, enriching, and courteous.
The next two links were selected to show that fundamental questions could either attract many answers [23] or just a few answers [24]. Regardless, the exchange of ideas will almost always be enriching. Even if there is no explicit guarantee of correctness, it is unlikely that grossly wrong answers will be permitted to prevail on Mathematics StackExchange.
Two other websites that discuss Binet’s formula, one with a mathematical flavour [25] and the other with a computing flavour [26] are worth a visit as well.

By now you would have realized that any references to the Fibonacci numbers can only give a limited and very partial glimpse into the subject. I am planning on writing further on the history and other aspects of these fascinating numbers, and will include additional relevant references in those blogs.

Epilogue

It was a good five months before I caught up with Sol after our encounter on the flight to Budapest. I told him that my conceptualization and fulfilment of his request had taken considerable effort and time.

“Next time, I will be more circumspect in acquiescing to your requests,” I told Sol.

“Did you yourself learn anything in the process?” he asked quizzically.

“Yes, of course,” I replied truthfully.

“Understand then, that as long as you keep learning, you are keeping fit mentally and intellectually. Have you ever taught anything to anyone without learning something yourself? Is this not true of even the simplest of ideas, like those of addition or multiplication?” Sol queried me.

I could not but agree.

That was when whatever regrets I had—of time spent and effort expended—in writing this blog on Binet’s formula, evaporated from my awareness. Explaining to another was definitely the surest form of learning and consolidating my own knowledge.

Acknowledgements

Since I work in splendid isolation, the AI chatbots proved to be very good mathematical companions along the way, as this blog took shape. The free resource of Wolfram Alpha is also cheerfully acknowledged.

I am especially grateful to my son, Nandakumar Chandrasekhar, for creating all the Julia scripts which are used in this blog, and which are freely downloadable by clicking on the hyperlinks.

Feedback

Please email me your comments and corrections.

A PDF version of this article is available for download here:

https://swanlotus.netlify.app/blogs/binet-s-formula.pdf

References

[1]

—. 2010. Arithmetic and geometric progressions. Mathcentre community project mcTY-apgp-2009-1. Retrieved 17 September 2025 from https://www.mathcentre.ac.uk/resources/uploaded/mc-ty-apgp-2009-1.pdf

[2]

Eric Weisstein. 2000. Binet’s Formula. Wolfram MathWorld. Retrieved 21 October 2025 from https://mathworld.wolfram.com/BinetsFormula.html

[3]

Oscar Levin. 2021. Discrete Mathematics. An Open Introduction (3rd edn). Retrieved 17 September 2025 from https://discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf

[4]

A R Wadsworth. 2017. Problems in Abstract Algebra. American Mathematical Society.

[5]

H E Huntley. 1970. The Divine Proportion: A Study in Mathematical Beauty. Dover Publications.

[6]

Katy Dobson and Alan Slomson. 2011. Proof by Induction. mathcentre community project mccp-dobson-2111. Retrieved 15 September 2025 from https://www.mathcentre.ac.uk/resources/uploaded/mathcentre-proof.pdf

[7]

Herbert S Wilf. 2006. generatingfunctionology (3rd edn). A K Peters.

[8]

Austin Rochford. 2013. Generating Functions and the Fibonacci Numbers. Retrieved 23 September 2025 from https://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html

[9]

Gilbert Strang. 2014. Differential Equations and Linear Algebra. Wellesley-Cambridge Press.

[10]

—. 2009. The inverse of a 2 × 2 matrix . mathcentre community project sigma-matrices7-2009-1. Retrieved 12 October 2025 from https://www.mathcentre.ac.uk/resources/uploaded/sigma-matrices7-2009-1.pdf

[11]

Ron Knott. The first 300 Fibonacci numbers, factored. Fibonacci Numbers and the Golden Section. Retrieved 22 October 2025 from https://r-knott.surrey.ac.uk/fibonacci/fibtable.html

[12]

—. 2025. List of Fibonacci numbers. MATH.net. Retrieved 22 October 2025 from https://www.math.net/list-of-fibonacci-numbers

[13]

Nick Higham. 2021. What Is a Companion Matrix?. Applied mathematics, numerical linear algebra and software. Retrieved 14 October 2025 from https://nhigham.com/2021/03/23/what-is-a-companion-matrix/

[14]

jordigh. 2013. I’ve always preferred to write Binet’s formula like this:. Hacker News. Retrieved 20 October 2025 from https://news.ycombinator.com/item?id=6660311

[15]

Ian Stewart. 2023. Galois Theory (5th edn). CRC Press.

[16]

John Swallow. 2004. Exploratory Galois Theory (1st edn). Cambridge University Press.

[17]

Ron Knott. Fibonacci Numbers and the Golden Section. This is the Home page for Dr Ron Knott’s multimedia web site on the Fibonacci numbers, the Golden section and the Golden string hosted by the Mathematics Department of the University of Surrey, UK. Retrieved 20 October 2025 from https://r-knott.surrey.ac.uk/fibonacci/fib.html

[18]

Alexander Bogomolny. 2018. Binet’s Formula via Generating Functions. Cut The Knot. Retrieved 26 September 2025 from https://www.cut-the-knot.org/blue/BinetFormula.shtml

[19]

—. The Fibonacci Quarterly. Official Publication of the Fibonacci Association. Retrieved 20 October 2025 from https://www.fq.math.ca/

[20]

Phil Nowell. 2005. Nth Term of the Fibonacci Sequence. Math Proofs Interesting mathematical results and elegant solutions to various problems. Retrieved 20 October 2025 from https://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci-sequence.html

[21]

Robin Houston. 2011. Computing Fibonacci numbers using Binet’s formula. Bosker Blog. Retrieved 20 October 2025 from https://bosker.wordpress.com/2011/07/27/computing-fibonacci-numbers-using-binet%E2%80%99s-formula/

[22]

yuv60. 2012. Origin of the constant ϕ in Binet’s formula of the n-th term of the Fibonacci sequence. Mathematics StackExchange. Retrieved 20 October 2025 from https://math.stackexchange.com/questions/268056/origin-of-the-constant-phi-in-binets-formula-of-the-n-th-term-of-the-fibon

[23]

Travis. 2017. What actually is a polynomial?. Mathematics StackExchange. Retrieved 20 October 2025 from https://math.stackexchange.com/questions/2185587/what-actually-is-a-polynomial/2185648#2185648

[24]

user56834. 2019. Polynomial vs power series vs formal power series?. Mathematics StackExchange. Retrieved 20 October 2025 from https://math.stackexchange.com/questions/3395044/polynomial-vs-power-series-vs-formal-power-series

[25]

—. 2025. Binet’s Formula. AoPS Online. Retrieved 18 October 2025 from https://artofproblemsolving.com/wiki/index.php/Binet's_Formula

[26]

rishabhprabhu. 2025. Nth Fibonacci Number using Binet’s Formula. GeeksforGeeks. Retrieved 20 October 2025 from https://www.geeksforgeeks.org/dsa/find-nth-fibonacci-number-using-binets-formula/

Binet is pronounced as bee-nay.↩︎
Fibonacci is pronounced as fi-buh-naa-chee.↩︎
Kindly review the blogs Differential Equations and Eigenvalues and Eigenvectors—Why are they important? if you need to these review concepts.↩︎
In my earlier blog Euler Two with Julia, I have discussed programs written in the Julia programming language that computed sums of the even-valued Fibonacci numbers whose values do not exceed four million. The interested reader is directed to that blog.↩︎
The qualifications are: homogeneous, linear, second order, constant coefficient, shift-invariant equations.↩︎
This has also been explained in my previous blog Eigenvalues and Eigenvectors—Why are they important?↩︎
See my blog Differential Equations.↩︎
See my blog Expressions, Equations, and Formulae.↩︎
In the process of researching for this blog, I came across a post by Austin Rochford [8] that is well written and that mirrors almost exactly the approach I had in mind.↩︎
The same result could have been obtained by use of the quadratic formula.↩︎
I have digressed thus far because I found the mathematical justification for Equation 33 on the basis of geometric series questionable where convergence cannot be asserted. It was only upon digging deeper did I stumble upon a different way of looking at the same expression. And the second viewpoint is the child of abstract algebra, which would not have found its way into most high school mathematical syllabuses.↩︎
See my blog Eigenvalues and Eigenvectors—Why are they important?.↩︎
See my blog The Two Most Important Numbers: Zero and One if this statement sounds cryptic to you.↩︎
Complex numbers also include real numbers.↩︎
See my blog A Tetrad of Captivating Problems to find out why.↩︎

Mathematics (17)