
The Fibonacci numbers are defined via a recurrence relation based on previous terms. This is sometimes called defining something inductively. However, we would like to develop a closed-form solution for the nth Fibonacci number. This paper shows how we calculate the nth Fibonacci number without a recurrence relation.
1 Motivation
The Fibonacci sequence first appeared in Leonardo of Pisa's Liber Abaci of 1202, as the solution to a problem about breeding rabbits. In modern notation it is defined by
$F_{0}=0, \quad F_{1}=1, \quad F_{n+1}=F_{n}+F_{n-1} \quad (n\ge1)$
producing
$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$
We call a definition of this kind recursive. Recursive definitions are often the most natural form and easy to understand, but they can sometimes be inconvenient. Imagine trying to calculate $F_{100}$; you would first need to calculate $F_{2}, F_{3}, ..., F_{99}$. Moreover, it is difficult to do any analysis of the sequence from the recurrence alone. Therefore, we often seek a closed form. In this paper, we walk through the proofs used by Binet to find the closed form given by
$F_{n}=\frac{\varphi^{n}-\psi^{n}}{\sqrt{5}},$
where
$\varphi=\frac{1+\sqrt{5}}{2}; \quad \psi=\frac{1-\sqrt{5}}{2} \quad \text{(1.2)}$
The heuristic that leads to this formula is empirical observation. Observe the ratios of consecutive terms:
$\frac{5}{3}\approx1.667, \quad \frac{8}{5}=1.600, \quad \frac{13}{8}=1.625, \quad \frac{21}{13}\approx1.615, \quad \frac{34}{21}\approx1.619.$
This suggests that the Fibonacci numbers behave, at least somewhat, like a geometric sequence, and that we can find geometric sequences meeting all of the needed criteria.
2 Mathematics
2.1 Preliminaries
Definition 2.1. Let $\mathcal{S}$ denote the set of real sequences $(a_{n})_{n\ge0}$ satisfying
$a_{n+1}=a_{n}+a_{n-1} \quad (n\ge1). \quad \text{(2.1)}$
Lemma 2.2 (Uniqueness). If $(a_{n}), (b_{n})\in\mathcal{S}$ with $a_{0}=b_{0}$ and $a_{1}=b_{1}$, then $a_{n}=b_{n}$ for all $n\ge0.$
Proof. Strong induction on $n$. The cases $n=0,1$ hold by hypothesis. If $a_{k}=b_{k}$ for all $k\le n,$ then
$a_{n+1}=a_{n}+a_{n-1}=b_{n}+b_{n-1}=b_{n+1}.$
2.2 Geometric solutions
Lemma 2.3. For $x\ne0,$ the sequence $a_{n}=x^{n}$ lies in $\mathcal{S}$ if and only if
$x^{2}=x+1. \quad \text{(2.2)}$
Proof. Substituting into (2.1) gives $x^{n+1}=x^{n}+x^{n-1}.$ Dividing by $x^{n-1}$ gives (2.2); multiplying (2.2) by $x^{n-1}$ gives the converse.
The roots of (2.2) are
$\varphi=\frac{1+\sqrt{5}}{2}; \quad \psi=\frac{1-\sqrt{5}}{2}.$
Lemma 2.4.
$\begin{aligned} \text{(i) } & \varphi^{2}=\varphi+1 \text{ and } \psi^{2}=\psi+1; \\ \text{(ii) } & \varphi+\psi=1 \text{ and } \varphi\psi=-1; \\ \text{(iii) } & \varphi-\psi=\sqrt{5} \end{aligned} \quad \text{(2.3)}$
Proof. (i) holds by (2.2). (ii) follows from $x^{2}-x-1=(x-\varphi)(x-\psi)$. (iii) follows from (2.2).
2.3 The solution set
Lemma 2.5 (Linearity). If $(a_{n}), (b_{n})\in\mathcal{S}$ and $A, B\in\mathbb{R}$, then $(Aa_{n}+Bb_{n})\in\mathcal{S}.$
Proof. $Aa_{n+1}+Bb_{n+1}=A(a_{n}+a_{n-1})+B(b_{n}+b_{n-1})=(Aa_{n}+Bb_{n})+(Aa_{n-1}+Bb_{n-1}).$
Proposition 2.6. Every $(a_{n})\in\mathcal{S}$ can be written uniquely as
$a_{n}=A\varphi^{n}+B\psi^{n} \quad \text{(2.4)}$
Proof. By Lemmas 2.3 and 2.5, (2.4) lies in $\mathcal{S}$. By Lemma 2.2, it suffices to solve
$A+B=a_{0}, \quad A\varphi+B\psi=a_{1}, \quad \text{(2.5)}$
which has a unique solution since $\det \begin{pmatrix}1&1\\ \varphi&\psi\end{pmatrix}=\psi-\varphi=-\sqrt{5}\ne0.$
2.4 Binet's formula
Theorem 2.7 (Binet). For every $n\ge0,$
$F_{n}=\frac{\varphi^{n}-\psi^{n}}{\sqrt{5}}$
Proof. Apply Proposition 2.6 with $a_{0}=0,$ $a_{1}=1.$ Then $B=-A,$ and
$A(\varphi-\psi)=1 \Rightarrow A=\frac{1}{\sqrt{5}}, \quad B=-\frac{1}{\sqrt{5}}.$
2.5 Verification for small indices
As a check, we evaluate Theorem 2.7 explicitly for $n=0,1,2,3$ using Lemma 2.4:
$\begin{aligned} n=0: &\quad \frac{\varphi^{0}-\psi^{0}}{\sqrt{5}}=\frac{1-1}{\sqrt{5}}=0=F_{0}, \\ n=1: &\quad \frac{\varphi-\psi}{\sqrt{5}}=\frac{\sqrt{5}}{\sqrt{5}}=1=F_{1}, \\ n=2: &\quad \frac{\varphi^{2}-\psi^{2}}{\sqrt{5}}=\frac{(\varphi-\psi)(\varphi+\psi)}{\sqrt{5}}=\frac{\sqrt{5}\cdot1}{\sqrt{5}}=1=F_{2}, \\ n=3: &\quad \frac{\varphi^{3}-\psi^{3}}{\sqrt{5}}=\frac{(2\varphi+1)-(2\psi+1)}{\sqrt{5}}=\frac{2(\varphi-\psi)}{\sqrt{5}}=2=F_{3}, \end{aligned}$
where $\varphi^{3}=\varphi\cdot\varphi^{2}=\varphi^{2}+\varphi=2\varphi+1$ and likewise $\psi^{3}=2\psi+1$.
References
[1] J. P. M. Binet, Mémoire sur l'intégration des équations linéaires aux différences finies, d'un ordre quelconque, à coefficients variables, Comptes Rendus de l'Académie des Sciences 17 (1843), 559-567.
[2] A. de Moivre, Miscellanea Analytica de Seriebus et Quadraturis, London, 1730.
[3] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994, §6.6 and §7.3.
[4] D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997, §1.2.8.
Disclaimer: AI assistance was used in preparing the LaTeX typesetting of this paper.


