The Fibonacci Numbers

The Fibonacci sequence $\{{𝑓}_{𝑛}\}$ is defined recursively by ${𝑓}_{1}={𝑓}_{2}=1$ and

{𝑓}_{𝑛}={𝑓}_{𝑛-1}+{𝑓}_{𝑛-2},\quad 𝑛\geq 3.

The value of each term is called a Fibonacci number. The first several Fibonacci numbers are

\begin{aligned}{𝑓}_{1} & =1, \\ {𝑓}_{2} & =1, \\ {𝑓}_{3} & ={𝑓}_{1}+{𝑓}_{2}=2, \\ {𝑓}_{4} & ={𝑓}_{2}+{𝑓}_{3}=3, \\ {𝑓}_{5} & ={𝑓}_{3}+{𝑓}_{4}=5, \\ {𝑓}_{6} & ={𝑓}_{4}+{𝑓}_{5}=8, \\ {𝑓}_{7} & ={𝑓}_{5}+{𝑓}_{6}=13, \\ {𝑓}_{8} & ={𝑓}_{6}+{𝑓}_{7}=21, \\ {𝑓}_{9} & ={𝑓}_{7}+{𝑓}_{8}=34, \\ {𝑓}_{10} & ={𝑓}_{8}+{𝑓}_{9}=55.\end{aligned}

We have many interesting identities related to Fibonacci numbers. Consider the partial sums of $\{{𝑓}_{𝑛}\}$ . Compute the first several terms:

\begin{aligned}{𝑠}_{1} & =1, \\ {𝑠}_{2} & ={𝑠}_{1}+{𝑓}_{2}=2, \\ {𝑠}_{3} & ={𝑠}_{2}+{𝑓}_{3}=4, \\ {𝑠}_{4} & ={𝑠}_{3}+{𝑓}_{4}=7, \\ {𝑠}_{5} & ={𝑠}_{4}+{𝑓}_{5}=12.\end{aligned}

Comparing with the first Fibonacci numebrs, it seems that each partial sum is just one less than some Fibonacci number. To be precise, we conjecture that

\sum _{𝑘=1}^{𝑛}{𝑓}_{𝑘}={𝑓}_{𝑛+2}-1.

(1.7)

The following is the proof, or more likely a derivation, of the formula in (1.7).

Inspired by the technique for summing a geometric sequence, let $𝑠={\sum }_{𝑘=1}^{𝑛}{𝑓}_{𝑘}$ . We write

$𝑠$	$=$	${𝑓}_{1}$	$+{𝑓}_{2}$	$+{𝑓}_{3}$	$+{𝑓}_{4}$	$+\cdots$	$+{𝑓}_{𝑛-1}$	$+{𝑓}_{𝑛}$
$𝑠$	$=$		${𝑓}_{1}$	$+{𝑓}_{2}$	$+{𝑓}_{3}$	$+\cdots$	$+{𝑓}_{𝑛-2}$	$+{𝑓}_{𝑛-1}$	$+{𝑓}_{𝑛}$
$2𝑠$	$=$	${𝑓}_{1}$	$+({𝑓}_{3}$	$+{𝑓}_{4}$	$+{𝑓}_{5}$	$+\cdots$	$+{𝑓}_{𝑛})$	$+{𝑓}_{𝑛+1}$	$+{𝑓}_{𝑛}$

It then follows that

\begin{aligned}2𝑠 & ={𝑓}_{1}+(𝑠-{𝑓}_{1}-{𝑓}_{2})+{𝑓}_{𝑛+1}+{𝑓}_{𝑛} \\ & =𝑠-{𝑓}_{2}+({𝑓}_{𝑛+1}+{𝑓}_{𝑛}) \\ & =𝑠-1+{𝑓}_{𝑛+2}.\end{aligned}

Subtract $𝑠$ from both sides:

𝑠=-1+{𝑓}_{𝑛+2}.

This is exactly (1.7).

Of course, we can also prove this by mathmetical induction. But it is less fun.

Proof

Let $𝑃(𝑛)$ be that (1.7) holds for all $𝑛\in {\mathbb{Z}}^{+}$ .

Base case. $𝑛=1$ . The LHS is ${𝑓}_{1}=1$ and RHS is ${𝑓}_{3}-1=2-1=1$ , and hence $𝑃(1)$ holds.

Inductive step. Assume $𝑃(𝑘)$ . When $𝑛=𝑘+1$ , we have

\begin{aligned}\sum _{𝑗=1}^{𝑘+1}{𝑓}_{𝑗} & = & & \sum _{𝑗=1}^{𝑘}{𝑓}_{𝑗}+{𝑓}_{𝑘+1} \\ & & & \text{Apply }\, 𝑃(𝑘) \\ & = & & ({𝑓}_{𝑘+2}-1)+{𝑓}_{𝑘+1} \\ & = & & ({𝑓}_{𝑘+1}+{𝑓}_{𝑘+2})-1 \\ & = & & {𝑓}_{𝑘+3}-1.\end{aligned}

This proves $𝑃(𝑘+1)$ .

How Fast Do Fibonacci Numbers Grow?

The following inequality shows that the Fibonacci sequence grows faster than a geometric sequence with common ratio $\varphi =\left(1+\sqrt{5}\right)/2$ , known as the golden ratio.

{𝑓}_{𝑛}>{\varphi }^{𝑛-2},\quad \forall 𝑛\geq 3.

(1.8)

Recall that the roots of the equation

{𝑥}^{2}-𝑥-1=0

are $\varphi =\left(1+\sqrt{5}\right)/2$ and $\left(1-\sqrt{5}\right)/2=-{\varphi }^{-1}$ . Hence one of the fundamental identities for $\varphi$ is

{\varphi }^{2}-\varphi -1=0.

(1.9)

We may use the second principle of mathematical induction to prove this.

Proof

Let $𝑃(𝑛)$ be that (1.8) holds.

Base case. The base cases are $𝑛=3$ and $𝑛=4$ .

When $𝑛=3$ , we have ${𝑓}_{3}=2$ and ${\varphi }^{3-2}=\varphi$ . Clearly $2>\varphi$ , and hence $𝑃(3)$ holds.

When $𝑛=4$ , we have ${𝑓}_{4}=3$ , and on the RHS we have ${\varphi }^{4-2}={\varphi }^{2}=\varphi +1$ , where the last step follows from (1.9). Since $3>\varphi +1$ , $𝑃(4)$ also holds.

Inductive step. Assume that $𝑃(𝑚)$ holds for all $3\leq 𝑚\leq 𝑘$ with $𝑘\geq 4$ . Let $𝑛=𝑘+1$ . We have

{𝑓}_{𝑛}={𝑓}_{𝑘+1}={𝑓}_{𝑘}+{𝑓}_{𝑘-1}.

Note that $𝑘>𝑘-1\geq 3$ . (This is exactly why we also include $𝑛=4$ as a base case.) Applying $𝑃(𝑘)$ and $𝑃(𝑘-1)$ , we obtain

\begin{aligned}{𝑓}_{𝑛}={𝑓}_{𝑘+1} & > & & {\varphi }^{𝑘-2}+{\varphi }^{𝑘-3} \\ & = & & {\varphi }^{𝑘-3}(\varphi +1) \\ & = & & {\varphi }^{𝑘-3}\cdot {\varphi }^{2} \\ & = & & {\varphi }^{𝑘-1}.\end{aligned}

This proves $𝑃(𝑘+1)$ .

Therefore, $𝑃(𝑛)$ holds for all $𝑛\geq 3$ .

We want an explicit formula for the $𝑛$ -th Fibonacci number ${𝑓}_{𝑛}$ . The bound above is already built from $\varphi$ , and the formula will be built from the same roots. The way in is the recurrence itself. It is linear, of degree $2$ , with constant coefficients, so we solve every recurrence of that shape and then return to ${𝑓}_{𝑛}$ .

A linear recurrence relation of degree $2$ with constant coefficients is an equation of the form

{𝑎}_{𝑛}={𝑐}_{1}{𝑎}_{𝑛-1}+{𝑐}_{2}{𝑎}_{𝑛-2},

where ${𝑐}_{1}$ and ${𝑐}_{2}$ are real numbers with ${𝑐}_{2}\neq 0$ . The Fibonacci recurrence is the case ${𝑐}_{1}={𝑐}_{2}=1$ .

Proposition 1.9

Suppose

{\lambda }^{2}-{𝑐}_{1}\lambda -{𝑐}_{2}=0

has two distinct roots ${\lambda }_{1}$ and ${\lambda }_{2}$ . A sequence ${\{{𝑎}_{𝑛}\}}_{𝑛\in \mathbb{N}}$ satisfies the homogeneous recurrence

{𝑎}_{𝑛}={𝑐}_{1}{𝑎}_{𝑛-1}+{𝑐}_{2}{𝑎}_{𝑛-2},\quad 𝑛\geq 2,

if and only if there are constants ${𝐶}_{1}$ and ${𝐶}_{2}$ such that

{𝑎}_{𝑛}={𝐶}_{1}{\lambda }_{1}^{𝑛}+{𝐶}_{2}{\lambda }_{2}^{𝑛},\quad 𝑛\in \mathbb{N}.

These constants are uniquely determined by ${𝑎}_{0}$ and ${𝑎}_{1}$ .

Proof

First take constants ${𝐶}_{1}$ and ${𝐶}_{2}$ , and set

{𝑏}_{𝑛}={𝐶}_{1}{\lambda }_{1}^{𝑛}+{𝐶}_{2}{\lambda }_{2}^{𝑛},\quad 𝑛\in \mathbb{N}.

For $𝑛\geq 2$ we have

\begin{aligned}{𝑏}_{𝑛} & ={𝐶}_{1}{\lambda }_{1}^{𝑛}+{𝐶}_{2}{\lambda }_{2}^{𝑛}, \\ {𝑏}_{𝑛-1} & ={𝐶}_{1}{\lambda }_{1}^{𝑛-1}+{𝐶}_{2}{\lambda }_{2}^{𝑛-1}, \\ {𝑏}_{𝑛-2} & ={𝐶}_{1}{\lambda }_{1}^{𝑛-2}+{𝐶}_{2}{\lambda }_{2}^{𝑛-2}.\end{aligned}

It then follows that

\begin{aligned}{𝑐}_{1}{𝑏}_{𝑛-1}+{𝑐}_{2}{𝑏}_{𝑛-2} & ={𝑐}_{1}{𝐶}_{1}{\lambda }_{1}^{𝑛-1}+{𝑐}_{1}{𝐶}_{2}{\lambda }_{2}^{𝑛-1}+{𝑐}_{2}{𝐶}_{1}{\lambda }_{1}^{𝑛-2}+{𝑐}_{2}{𝐶}_{2}{\lambda }_{2}^{𝑛-2} \\ & ={𝐶}_{1}({𝑐}_{1}{\lambda }_{1}^{𝑛-1}+{𝑐}_{2}{\lambda }_{1}^{𝑛-2})+{𝐶}_{2}({𝑐}_{1}{\lambda }_{2}^{𝑛-1}+{𝑐}_{2}{\lambda }_{2}^{𝑛-2}) \\ & ={𝐶}_{1}{\lambda }_{1}^{𝑛-2}({𝑐}_{1}{\lambda }_{1}+{𝑐}_{2})+{𝐶}_{2}{\lambda }_{2}^{𝑛-2}({𝑐}_{1}{\lambda }_{2}+{𝑐}_{2}).\end{aligned}

Since ${\lambda }_{1}$ and ${\lambda }_{2}$ satisfy ${\lambda }^{2}-{𝑐}_{1}\lambda -{𝑐}_{2}=0$ , we have ${𝑐}_{1}\lambda +{𝑐}_{2}={\lambda }^{2}$ . Therefore

\begin{aligned}{𝑐}_{1}{𝑏}_{𝑛-1}+{𝑐}_{2}{𝑏}_{𝑛-2} & ={𝐶}_{1}{\lambda }_{1}^{𝑛-2}({𝑐}_{1}{\lambda }_{1}+{𝑐}_{2})+{𝐶}_{2}{\lambda }_{2}^{𝑛-2}({𝑐}_{1}{\lambda }_{2}+{𝑐}_{2}) \\ & ={𝐶}_{1}{\lambda }_{1}^{𝑛}+{𝐶}_{2}{\lambda }_{2}^{𝑛} \\ & ={𝑏}_{𝑛}.\end{aligned}

Every sequence of this form satisfies the recurrence.

Conversely, suppose $\{{𝑎}_{𝑛}\}$ satisfies the recurrence. We look for constants ${𝐶}_{1}$ and ${𝐶}_{2}$ for which ${𝑏}_{𝑛}={𝐶}_{1}{\lambda }_{1}^{𝑛}+{𝐶}_{2}{\lambda }_{2}^{𝑛}$ has the same first two terms:

\begin{aligned}{𝐶}_{1}+{𝐶}_{2} & ={𝑎}_{0}, \\ {𝐶}_{1}{\lambda }_{1}+{𝐶}_{2}{\lambda }_{2} & ={𝑎}_{1}.\end{aligned}

Multiply the first equation by ${\lambda }_{2}$ and subtract from the second:

{𝐶}_{1}({\lambda }_{1}-{\lambda }_{2})={𝑎}_{1}-{𝑎}_{0}{\lambda }_{2}.

The same subtraction with ${\lambda }_{1}$ in place of ${\lambda }_{2}$ yields

{𝐶}_{2}({\lambda }_{2}-{\lambda }_{1})={𝑎}_{1}-{𝑎}_{0}{\lambda }_{1}.

The roots are distinct, so we may divide:

{𝐶}_{1}=\frac{{𝑎}_{1}-{𝑎}_{0}{\lambda }_{2}}{{\lambda }_{1}-{\lambda }_{2}},\quad {𝐶}_{2}=\frac{{𝑎}_{0}{\lambda }_{1}-{𝑎}_{1}}{{\lambda }_{1}-{\lambda }_{2}}.

With these constants, ${𝑏}_{0}={𝑎}_{0}$ and ${𝑏}_{1}={𝑎}_{1}$ , and the first part says that $\{{𝑏}_{𝑛}\}$ satisfies the recurrence.

We claim ${𝑎}_{𝑛}={𝑏}_{𝑛}$ for every $𝑛\in \mathbb{N}$ . The cases $𝑛=0$ and $𝑛=1$ hold by the choice of ${𝐶}_{1}$ and ${𝐶}_{2}$ . Fix $𝑛\geq 2$ , and assume ${𝑎}_{𝑘}={𝑏}_{𝑘}$ for all $𝑘<𝑛$ . Then

{𝑎}_{𝑛}={𝑐}_{1}{𝑎}_{𝑛-1}+{𝑐}_{2}{𝑎}_{𝑛-2}={𝑐}_{1}{𝑏}_{𝑛-1}+{𝑐}_{2}{𝑏}_{𝑛-2}={𝑏}_{𝑛}.

Thus ${𝑎}_{𝑛}={𝑏}_{𝑛}$ for every $𝑛$ , and the constants are the ones just found from ${𝑎}_{0}$ and ${𝑎}_{1}$ .

We now return to the Fibonacci numbers, the case ${𝑐}_{1}={𝑐}_{2}=1$ . Proposition 1.9 is indexed from $𝑛=0$ , so set ${𝑓}_{0}=0$ . Then ${𝑓}_{2}={𝑓}_{1}+{𝑓}_{0}$ , and the recurrence holds for every $𝑛\geq 2$ :

{𝑓}_{𝑛}={𝑓}_{𝑛-1}+{𝑓}_{𝑛-2},\quad 𝑛\geq 2.

The quadratic of Proposition 1.9 is therefore

{\lambda }^{2}-\lambda -1=0,

the same equation whose roots we computed above,

{\lambda }_{1}=\varphi =\frac{1+\sqrt{5}}{2}\quad \text{and}\quad {\lambda }_{2}=-{\varphi }^{-1}=\frac{1-\sqrt{5}}{2}.

Hence

{𝑓}_{𝑛}={𝐶}_{1}{\lambda }_{1}^{𝑛}+{𝐶}_{2}{\lambda }_{2}^{𝑛}.

The initial terms fix the constants. From ${𝑓}_{0}=0$ and ${𝑓}_{1}=1$ ,

\begin{aligned}{𝐶}_{1}+{𝐶}_{2} & =0, \\ {𝐶}_{1}{\lambda }_{1}+{𝐶}_{2}{\lambda }_{2} & =1.\end{aligned}

The first equation gives ${𝐶}_{2}=-{𝐶}_{1}$ , and the second becomes ${𝐶}_{1}({\lambda }_{1}-{\lambda }_{2})=1$ . Since ${\lambda }_{1}-{\lambda }_{2}=\sqrt{5}$ , we obtain ${𝐶}_{1}=1/\sqrt{5}$ and ${𝐶}_{2}=-1/\sqrt{5}$ . With ${\lambda }_{2}=-{\varphi }^{-1}$ , this is

{𝑓}_{𝑛}=\frac{1}{\sqrt{5}}({\lambda }_{1}^{𝑛}-{\lambda }_{2}^{𝑛})=\frac{1}{\sqrt{5}}({\varphi }^{𝑛}-{(-\varphi )}^{-𝑛}),\quad 𝑛\in \mathbb{N}.

The ratio of two consecutive terms is

\frac{{𝑓}_{𝑛+1}}{{𝑓}_{𝑛}}=\frac{{\varphi }^{𝑛+1}-{(-\varphi )}^{-𝑛-1}}{{\varphi }^{𝑛}-{(-\varphi )}^{-𝑛}}=\frac{\varphi -{(-1)}^{-𝑛-1}{\varphi }^{-2𝑛-1}}{1-{(-1)}^{-𝑛}{\varphi }^{-2𝑛}}.

Since $\varphi >1$ , when $𝑛\to \infty$ , the limit of the ratio ${𝑓}_{𝑛+1}/{𝑓}_{𝑛}$ exists and is precisely equal to the golden ratio $\varphi$ .

The same recurrence gives another perspective, and a construction of ${𝑎}_{𝑛}$ , by writing one step as matrix multiplication:

\begin{pmatrix}{𝑎}_{𝑛} \\ {𝑎}_{𝑛-1}\end{pmatrix}=\begin{pmatrix}{𝑐}_{1} & {𝑐}_{2} \\ 1 & 0\end{pmatrix}\begin{pmatrix}{𝑎}_{𝑛-1} \\ {𝑎}_{𝑛-2}\end{pmatrix}.

Iterating all the way down to the initial terms, we have

\begin{pmatrix}{𝑎}_{𝑛} \\ {𝑎}_{𝑛-1}\end{pmatrix}={\begin{pmatrix}{𝑐}_{1} & {𝑐}_{2} \\ 1 & 0\end{pmatrix}}^{𝑛-1}\begin{pmatrix}{𝑎}_{1} \\ {𝑎}_{0}\end{pmatrix}.

The expression is settled once we can simplify the power

{\begin{pmatrix}{𝑐}_{1} & {𝑐}_{2} \\ 1 & 0\end{pmatrix}}^{𝑛-1}.

One who knows linear algebra will at once think of diagonalization and eigenvalues. Those eigenvalues are the roots ${\lambda }_{1}$ and ${\lambda }_{2}$ of the quadratic in Proposition 1.9, so the matrix power leads back to the same closed form. We will not pursue that here.