1 Introduction

I recently came across a fact about the Fibonacci sequence that I'd not encountered before. It goes something like:

If you do (something not quite trivial) to the Fibonacci sequence you get $\frac{1}{89}$.

Now, I'm not the biggest fan of the Fibonacci sequence so my immediate reaction to this was to look for a more general picture to fit this into. I did see a proof of this fact, and it gave me the hint as to that wider story.

2 Geometric Series

The "something not quite trivial" was described as shifting each Fibonacci number down below the decimal point so that each one is one further down than the previous. Then adding them.

$$\begin{array}{rl}& \phantom{+}0.01\\ & +0.001\\ & +0.0002\\ & +0.00003\\ & +0.000005\\ & +0.0000008\\ & +0.00000013\\ & +\dots \end{array}$$

The result is $\frac{1}{89}$.

A more mathematical description of this procedure is to sum the series $\frac{F_n}{{10}^n}$. It makes the numbers work a little easier if we index our series starting at $0$, and we start the Fibonacci sequence with $F_0=0$ and $F_1=1$. With this convention, we're looking at the series:

$${\sum }_{n=0}^{\mathrm{\infty }}\frac{F_n}{{10}^{n+1}}$$

Now the Fibonacci sequence is almost a geometric series with common ratio $\varphi =\frac{1+\sqrt{5}}{2}$. More precisely, we have:

$$F_n=\frac{{\varphi }^n-(-\varphi {)}^{-n}}{\sqrt{5}}$$

So we're summing:

$$\frac{F_n}{{10}^{n+1}}=\frac{{\varphi }^n-(-\varphi {)}^{-n}}{{10}^{n+1}\sqrt{5}}=\frac{1}{10\sqrt{5}}(\frac{\varphi }{10}{)}^n-\frac{1}{10\sqrt{5}}(\frac{-1}{10\varphi }{)}^n$$

Using the sum of a geometric series, we therefore get:

$$\begin{array}{rl}\sum \frac{F_n}{{10}^{n+1}}& =\frac{1}{10\sqrt{5}}\left(\frac{1}{1-\frac{\varphi }{10}}\right)-\frac{1}{10\sqrt{5}}\left(\frac{1}{1+\frac{1}{10\varphi }}\right)\\ & =\frac{1}{\sqrt{5}}\left(\frac{1}{10-\varphi }\right)-\frac{1}{\sqrt{5}}\left(\frac{1}{10+{\varphi }^{-1}}\right)\\ & =\frac{1}{\sqrt{5}}(\frac{1}{10-\varphi }-\frac{1}{10+{\varphi }^{-1}})\\ & =\frac{1}{\sqrt{5}}\left(\frac{(10+{\varphi }^{-1})-(10-\varphi )}{(10-\varphi )(10+{\varphi }^{-1})}\right)\\ & =\frac{1}{\sqrt{5}}\left(\frac{10+{\varphi }^{-1}-10+\varphi }{100-10(\varphi -{\varphi }^{-1})-1}\right)\\ & =\frac{1}{\sqrt{5}}\left(\frac{{\varphi }^{-1}+\varphi }{100-10(\varphi -{\varphi }^{-1})-1}\right)\\ \end{array}$$

Now $\varphi =\frac{1+\sqrt{5}}{2}$ and $-{\varphi }^{-1}=\frac{1-\sqrt{5}}{2}$ so:

$$\begin{array}{rl}{\varphi }^{-1}+\varphi & =\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}=\frac{1+\sqrt{5}-1+\sqrt{5}}{2}=\frac{2\sqrt{5}}{2}=\sqrt{5}\\ \varphi -{\varphi }^{-1}& =\frac{1+\sqrt{5}}{2}+\frac{1-\sqrt{5}}{2}=\frac{1+\sqrt{5}+1-\sqrt{5}}{2}=\frac{2}{2}=1\end{array}$$

Hence:

$$\sum \frac{F_n}{{10}^{n+1}}=\frac{1}{\sqrt{5}}\frac{\sqrt{5}}{100-10-1}=\frac{1}{100-10-1}$$

3 Generalising Fibonacci

The construction works with more sequences than just Fibonacci's. In this section we'll consider two variations. The first is to Lucas sequences. The second is to consider a sequence formed by adding three terms together.

First, let us consider Lucas sequences. These are defined by choosing integers $P$ and $Q$ and applying the recursive relation:

$$a_{n+1}=P{a}_n-Q{a}_{n-1}$$

We need to choose suitable starting terms, we'll take $a_0=0$ and $a_1=1$.

Consider the quadratic $x^2-Px+Q$ and let $\alpha$ and $\beta$ be its roots1. It turns out that the sequence $(a_n)$ can be written as:

$$a_n=\frac{{\alpha }^n-{\beta }^n}{\alpha -\beta }.$$

Now choose $q$ such that $\left|q\right|>\left|\alpha \right|$ and $\left|q\right|>\left|\beta \right|$. Consider the series

$$\sum \frac{a_n}{q^{n+1}}$$

using the above expression for $a_n$, this simplifies as follows:

$$\begin{array}{rl}\sum \frac{a_n}{q^{n+1}}& =\sum \frac{1}{q(\alpha -\beta )}\left(\right(\frac{\alpha }{q}{)}^n-\left(\frac{\beta }{q}{)}^n\right)\\ & =\frac{1}{q(\alpha -\beta )}(\sum (\frac{\alpha }{q}{)}^n-\sum \left(\frac{\beta }{q}{)}^n\right)\\ & =\frac{1}{q(\alpha -\beta )}(\frac{1}{1-\frac{\alpha }{q}}-\frac{1}{1-\frac{\beta }{q}})\\ & =\frac{1}{\alpha -\beta }(\frac{1}{q-\alpha }-\frac{1}{q-\beta })\\ & =\frac{1}{\alpha -\beta }\left(\frac{(q-\beta )-(q-\alpha )}{(q-\alpha )(q-\beta )}\right)\\ & =\frac{1}{\alpha -\beta }\left(\frac{q-\beta -q+\alpha }{q^2-(\alpha +\beta )q+\alpha \beta }\right)\\ & =\frac{1}{\alpha -\beta }\left(\frac{\alpha -\beta }{q^2-(\alpha +\beta )q+\alpha \beta }\right)\\ & =\frac{1}{q^2-(\alpha +\beta )q+\alpha \beta }\\ \end{array}$$

Now $\alpha$ and $\beta$ are the roots of the quadratic $x^2-Px+U$ and so $\alpha +\beta =P$ and $\alpha \beta =U$. Thus:

$$\sum \frac{a_n}{q^{n+1}}=\frac{1}{q^2-Pq+U}$$

Now let's take this up one level. Choose $A$, $B$, and $C$ and define the sequence $(b_n)$ by $b_0=0$, $b_1=0$, $b_2=1$ and

$$b_{n+1}=A{b}_n-B{b}_{n-1}+C{b}_{n-2}$$

Let $\alpha$, $\beta$, and $\gamma$ be the roots of $x^3-A{x}^2+Bx-C$. Then there are $a$, $b$, and $c$ such that:

$$b_n=a{\alpha }^n+b{\beta }^n+c{\gamma }^n$$

A bit of tedious simultaneous equation solving shows that:

$$b_n=\frac{(\gamma -\beta ){\alpha }^n+(\alpha -\gamma ){\beta }^n+(\beta -\alpha ){\gamma }^n}{(\alpha -\beta )(\beta -\gamma )(\gamma -\alpha )}$$

Let $q$ be such that $\left|q\right|>\left|\alpha \right|,\left|\beta \right|,\left|\gamma \right|$. Then:

$$\begin{array}{rl}\sum \frac{b_n}{q^{n+1}}& =\frac{1}{q(\alpha -\beta )(\beta -\gamma )(\gamma -\alpha )}(\sum (\gamma -\beta )(\frac{\alpha }{q}{)}^n+\sum (\alpha -\gamma )(\frac{\beta }{q}{)}^n+\sum (\beta -\alpha )(\frac{\gamma }{q}{)}^n)\\ & =\frac{1}{q(\alpha -\beta )(\beta -\gamma )(\gamma -\alpha )}(\frac{\gamma -\beta }{1-\frac{\alpha }{q}}+\frac{\alpha -\gamma }{1-\frac{\beta }{q}}+\frac{\beta -\alpha }{1-\frac{\gamma }{q}})\\ & =\frac{1}{(\alpha -\beta )(\beta -\gamma )(\gamma -\alpha )}(\frac{\gamma -\beta }{q-\alpha }+\frac{\alpha -\gamma }{q-\beta }+\frac{\beta -\alpha }{q-\gamma })\\ & =\frac{1}{(\alpha -\beta )(\beta -\gamma )(\gamma -\alpha )}\frac{(\gamma -\beta )(q-\beta )(q-\alpha )+(\alpha -\gamma )(q-\alpha )(q-\beta )+(\beta -\alpha )(q-\beta )(q-\alpha )}{(q-\alpha )(q-\beta )(q-\gamma )}\end{array}$$

Now the numerator of that horrendous-looking fraction simplifies considerably. When expanded out, all the terms with $q$ or $q^2$ cancel leaving only:

$$\beta {\gamma }^2-{\beta }^2\gamma +{\alpha }^2\gamma -\alpha {\gamma }^2+\alpha {\beta }^2-{\alpha }^2\beta$$

Multiplying out $(\alpha -\beta )(\beta -\gamma )(\gamma -\alpha )$ leads to exactly the same expression, resulting in:

$$\sum \frac{b_n}{q^{n+1}}=\frac{1}{(q-\alpha )(q-\beta )(q-\gamma )}$$

We recognise the denominator as the polynomial $q^3-A{q}^2+Bq-C$, whence:

$$\sum \frac{b_n}{q^{n+1}}=\frac{1}{q^3-A{q}^2+Bq-C}$$

There seems to be a pattern emerging.

4 Matrices

In the analysis of the cubic version we hid most of the algebra. So proving that the pattern continues looks like it might get quite tedious unless we can figure out a way to simplify it. Fortunately, there is a way to do so which involves making the series purely geometric rather than a sum of geometric series. We'll start back with the Fibonacci sequence.

The trick is to introduce matrices. Let:

$$A=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$$

then

$$A\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}y\\ x+y\end{array}\right]$$

so feeding in the Fibonacci sequence we get

$$A\left[\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right]=\left[\begin{array}{c}{F}_{n+1}\\ F_n+F_{n+1}\end{array}\right]=\left[\begin{array}{c}{F}_{n+1}\\ F_{n+2}\end{array}\right]$$

thus putting $u_n=\left[\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right]$ we get $A{u}_n=u_{n+1}$.

Our sum is therefore closely related to the sum:

$$\sum \frac{1}{{10}^{n+1}}{u}_n=\sum \frac{1}{{10}^{n+1}}{A}^n{u}_0=(\sum (\frac{1}{10}A{)}^n)\frac{u_0}{10}$$

5 Spectral Theory

There was nothing particularly special about the particular matrix $A$ in the previous section. What we needed was for the sum to converge and that's to do with the relationship between $A$ and $\frac{1}{10}$.

Let's generalise further. We have a matrix $A$, a number $q$, and a starting vector $u_0$. We consider the sum:

$$\sum q^{-n-1}{A}^n{u}_0=q^{-1}(\sum (q^{-1}A{)}^n)u_0$$

The rule for this to converge is similar to the convergence of a geometric sum of numbers. We need the "size" of $q^{-1}A$ to be less than $1$. 2

For the Fibonacci matrix this is true providing $q>\varphi$ so $q=10$ certainly qualifies.

When this is true, the same analysis as for ordinary geometric series gives:

$$(I-q^{-1}A)\sum (q^{-1}A{)}^n=I+q^{-1}A+q^{-2}{A}^2+\dots -q^{-1}A-q^{-2}{A}^2-\dots =I$$

The condition on $q$ means that $I-q^{-1}A$ is invertible and so

$$\sum q^{-n}{A}^n=(I-q^{-1}A{)}^{-1}$$

Putting in the extra factor of $q^{-1}$ yields:

$$\sum q^{-n-1}{A}^n=(qI-A{)}^{-1}$$

Looking at when the expression $(qI-A{)}^{-1}$ makes sense is the start of an area of Mathematics called Spectral Theory.

6 Back to Fibonacci

In the Fibonacci situation, the matrix $A$ is

$$\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$$

so $qI-A$ is

$$\left[\begin{array}{cc}q& -1\\ -1& q-1\end{array}\right]$$

which has inverse

$$\frac{1}{\det (qI-A)}\left[\begin{array}{cc}q-1& 1\\ 1& q\end{array}\right]$$

The determinant $\det (tI-A)$ is known as the characteristic polynomial of $A$ and is written $c_A(t)$. For the Fibonacci matrix, this is $c_A(t)=t(t-1)-1=t^2-t-1$.

Putting in $q=10$ we get:

$$c_A(10)={10}^2-10-1=100-10-1=89$$

which is the source of the $89$.

Applying this to the initial vector, $u_0=\left[\begin{array}{c}{F}_0\\ F_1\end{array}\right]=\left[\begin{array}{c}0\\ 1\end{array}\right]$ we get

$$(qI-A{)}^{-1}{u}_0=\frac{1}{q^2-q-1}[\begin{array}{cc}q-1& 1\\ 1& q\end{array}\left]\right[\begin{array}{c}0\\ 1\end{array}]=\frac{1}{q^2-q-1}[\begin{array}{c}1\\ q\end{array}]$$

In terms of the summation, we have:

$$\sum q^{-n-1}{A}^n{u}_0=\sum q^{-n-1}{u}_n=\sum q^{-n-1}\left[\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right]=\left[\begin{array}{c}\sum q^{-n-1}{F}_n\\ \sum q^{-n-1}{F}_{n+1}\end{array}\right]$$

Equating terms gives

$$\frac{1}{q^2-q-1}=\sum q^{-n-1}{F}_n$$

Putting in $q=10$, we get:

$$\frac{1}{89}=\sum {10}^{-n-1}{F}_n$$

as claimed.

This formula works providing $\left|q\right|>\frac{1+\sqrt{5}}{2}$. In particular, it works for any positive whole number at least $2$. So if we did the same construction in a different base we could use the same analysis to figure out the sum.

In particular, we see that if we had worked in base $2$ we would have gotten the answer $1$. That is,

$$\sum \frac{1}{2^{n+1}}{F}_n=1$$

The other slightly surprising thing is how many of these entries are prime. It does start dropping off after $12$, though.

There is another way to look at the denominator which is to see that in base $n$, we would write $c_A(n)$ as:

$$c_A(n)={100}_n-{10}_n-1_n$$

where the subscript means that the representation is to be understood in base $n$.

7 The General Case

The general case is to have a sequence $(a_n)$ defined by a rule:

$$a_{n+1}=c_1{a}_n+c_2{a}_{n-1}+\dots +c_k{a}_{n+1-k}$$

and starting conditions $a_0=a_1=\dots =a_{k-2}=0$, $a_{k-1}=1$.

The associated matrix is

$$A=\left[\begin{array}{ccccc}0& 1& 0& \dots & 0\\ 0& 0& 1& \dots & 0\\ ⋮& ⋮& ⋮& & ⋮\\ 0& 0& 0& \dots & 1\\ c_k& c_{k-1}& c_{k-2}& \dots & c_1\end{array}\right]$$

We're interested in $qI-A$, which is:

$$qI-A=\left[\begin{array}{ccccc}q& -1& 0& \dots & 0\\ 0& q& -1& \dots & 0\\ ⋮& ⋮& ⋮& & ⋮\\ 0& 0& 0& \dots & -1\\ -c_k& -c_{k-1}& -c_{k-2}& \dots & q-c_1\end{array}\right]$$

Although it appears that we want to invert $qI-A$, we actually only want to work out $(qI-A{)}^{-1}{u}_0$, where

$$u_0=\left[\begin{array}{c}0\\ ⋮\\ 0\\ 1\end{array}\right]$$

which means that we want to solve the system

$$\left[\begin{array}{ccccc}q& -1& 0& \dots & 0\\ 0& q& -1& \dots & 0\\ ⋮& ⋮& ⋮& & ⋮\\ 0& 0& 0& \dots & -1\\ -c_k& -c_{k-1}& -c_{k-2}& \dots & q-c_1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ ⋮\\ x_k\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\\ ⋮\\ 1\end{array}\right]$$

Normally we would solve this by Gaussian Elimination, but this system can be solved more directly since the first $k-1$ equations read:

$$q{x}_j-x_{j+1}=0$$

and thus $x_{j+1}=q{x}_j=q^j{x}_1$.

The final equation reads:

$$-c_k{x}_1-c_{k-1}{x}_2-c_{k-2}{x}_3-\dots +(q-c_1)x_k=1$$

substituting in, we get:

$$-c_k{x}_1-c_{k-1}q{x}_1-c_{k-2}{q}^2{x}_1-\dots -c_1{q}^{k-1}{x}_1+q^k{x}_1=1$$

whence

$$x_1=\frac{1}{q^k-c_1{q}^{k-1}-\dots c_{k-2}{q}^2-c_{k-1}q-c_k}$$

Note that $t^k-c_1{t}^{k-1}-\dots c_{k-2}{t}^2-c_{k-1}t-c_k$ is the characteristic polynomial of $A$.

Now the first component of $\sum q^{-n-1}{A}^n{u}_0$ is $\sum q^{-n-1}{a}_n$ and so

$$\sum q^{-n-1}{a}_n=\frac{1}{q^k-c_1{q}^{k-1}-\dots c_{k-2}{q}^2-c_{k-1}q-c_k}$$

Note that this is only valid if $q$ is bigger in magnitude than any of the roots of $t^k-c_1{t}^{k-1}-\dots -c_{k-1}$.

For a finale, let's try a triple Fibonacci where each term is the sum of the preceding three:

$$b_{n+1}=b_n+b_{n-1}+b_{n-2}$$

Starting at $b_0=0$, $b_1=0$, $b_2=0$, the first terms of this sequence are:

$$0,0,1,1,2,4,7,13,24,44,\dots$$

The matrix in that case is:

$$\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]$$

and the characteristic polynomial of this is

$$c(t)=t^3-t^2-t-1$$

hence:

$$\sum q^{-n-1}{b}_n=\frac{1}{q^3-q^2-q-1}$$

Interestingly, this is valid for $q=10$ and for $q=2$ and we get:

$$\begin{array}{rl}\sum {10}^{-n-1}{b}_n& =\frac{1}{1000-100-10-1}=\frac{1}{889},\\ \sum 2^{-n-1}{b}_n& =1.\end{array}$$