Summing Up Fibonacci

loopspace

2017-11-03

Creative Commons License

Contents

  1. Home

  2. 1. Introduction

  3. 2. Geometric Series

  4. 3. Generalising Fibonacci

  5. 4. Matrices

  6. 5. Spectral Theory

  7. 6. Back to Fibonacci

  8. 7. The General Case

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 189.

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.

+0.01+0.001+0.0002+0.00003+0.000005+0.0000008+0.00000013+

The result is 189.

A more mathematical description of this procedure is to sum the series Fn10n. It makes the numbers work a little easier if we index our series starting at 0, and we start the Fibonacci sequence with F0=0 and F1=1. With this convention, we're looking at the series:

n=0Fn10n+1

Now the Fibonacci sequence is almost a geometric series with common ratio ϕ=1+52. More precisely, we have:

Fn=ϕn-(-ϕ)-n5

So we're summing:

Fn10n+1=ϕn-(-ϕ)-n10n+15=1105(ϕ10)n-1105(-110ϕ)n

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

Fn10n+1=1105(11-ϕ10)-1105(11+110ϕ)=15(110-ϕ)-15(110+ϕ-1)=15(110-ϕ-110+ϕ-1)=15((10+ϕ-1)-(10-ϕ)(10-ϕ)(10+ϕ-1))=15(10+ϕ-1-10+ϕ100-10(ϕ-ϕ-1)-1)=15(ϕ-1+ϕ100-10(ϕ-ϕ-1)-1)

Now ϕ=1+52 and -ϕ-1=1-52 so:

ϕ-1+ϕ=1+52-1-52=1+5-1+52=252=5ϕ-ϕ-1=1+52+1-52=1+5+1-52=22=1

Hence:

Fn10n+1=155100-10-1=1100-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:

an+1=Pan-Qan-1

We need to choose suitable starting terms, we'll take a0=0 and a1=1.

Consider the quadratic x2-Px+Q and let α and β be its roots1. It turns out that the sequence (an) can be written as:

1The analysis works fine if α and β are complex, but needs a little adjustment if there is a repeated root.

an=αn-βnα-β.

Now choose q such that |q|>|α| and |q|>|β|. Consider the series

anqn+1

using the above expression for an, this simplifies as follows:

anqn+1=1q(α-β)((αq)n-(βq)n)=1q(α-β)((αq)n-(βq)n)=1q(α-β)(11-αq-11-βq)=1α-β(1q-α-1q-β)=1α-β((q-β)-(q-α)(q-α)(q-β))=1α-β(q-β-q+αq2-(α+β)q+αβ)=1α-β(α-βq2-(α+β)q+αβ)=1q2-(α+β)q+αβ

Now α and β are the roots of the quadratic x2-Px+U and so α+β=P and αβ=U. Thus:

anqn+1=1q2-Pq+U

Now let's take this up one level. Choose A, B, and C and define the sequence (bn) by b0=0, b1=0, b2=1 and

bn+1=Abn-Bbn-1+Cbn-2

Let α, β, and γ be the roots of x3-Ax2+Bx-C. Then there are a, b, and c such that:

bn=aαn+bβn+cγn

A bit of tedious simultaneous equation solving shows that:

bn=(γ-β)αn+(α-γ)βn+(β-α)γn(α-β)(β-γ)(γ-α)

Let q be such that |q|>|α|,|β|,|γ|. Then:

bnqn+1=1q(α-β)(β-γ)(γ-α)((γ-β)(αq)n+(α-γ)(βq)n+(β-α)(γq)n)=1q(α-β)(β-γ)(γ-α)(γ-β1-αq+α-γ1-βq+β-α1-γq)=1(α-β)(β-γ)(γ-α)(γ-βq-α+α-γq-β+β-αq-γ)=1(α-β)(β-γ)(γ-α)(γ-β)(q-β)(q-α)+(α-γ)(q-α)(q-β)+(β-α)(q-β)(q-α)(q-α)(q-β)(q-γ)

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

βγ2-β2γ+α2γ-αγ2+αβ2-α2β

Multiplying out (α-β)(β-γ)(γ-α) leads to exactly the same expression, resulting in:

bnqn+1=1(q-α)(q-β)(q-γ)

We recognise the denominator as the polynomial q3-Aq2+Bq-C, whence:

bnqn+1=1q3-Aq2+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=[0111]

then

A[xy]=[yx+y]

so feeding in the Fibonacci sequence we get

A[FnFn+1]=[Fn+1Fn+Fn+1]=[Fn+1Fn+2]

thus putting un=[FnFn+1] we get Aun=un+1.

Our sum is therefore closely related to the sum:

110n+1un=110n+1Anu0=((110A)n)u010

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 110.

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

q-n-1Anu0=q-1((q-1A)n)u0

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

2Specifically, we need q>A where is the operator norm.

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

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

(I-q-1A)(q-1A)n=I+q-1A+q-2A2+-q-1A-q-2A2-=I

The condition on q means that I-q-1A is invertible and so

q-nAn=(I-q-1A)-1

Putting in the extra factor of q-1 yields:

q-n-1An=(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

[0111]

so qI-A is

[q-1-1q-1]

which has inverse

1det(qI-A)[q-111q]

The determinant det(tI-A) is known as the characteristic polynomial of A and is written cA(t). For the Fibonacci matrix, this is cA(t)=t(t-1)-1=t2-t-1.

Putting in q=10 we get:

cA(10)=102-10-1=100-10-1=89

which is the source of the 89.

Applying this to the initial vector, u0=[F0F1]=[01] we get

(qI-A)-1u0=1q2-q-1[q-111q][01]=1q2-q-1[1q]

In terms of the summation, we have:

q-n-1Anu0=q-n-1un=q-n-1[FnFn+1]=[q-n-1Fnq-n-1Fn+1]

Equating terms gives

1q2-q-1=q-n-1Fn

Putting in q=10, we get:

189=10-n-1Fn

as claimed.

This formula works providing |q|>1+52. 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.

Base Sum
2 1
3 15
4 111
5 119
6 129
7 141
8 155
9 171
10 189
11 1119
12 1131

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

12n+1Fn=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 cA(n) as:

cA(n)=100n-10n-1n

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 (an) defined by a rule:

an+1=c1an+c2an-1++ckan+1-k

and starting conditions a0=a1==ak-2=0, ak-1=1.

The associated matrix is

A=[010000100001ckck-1ck-2c1]

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

qI-A=[q-1000q-10000-1-ck-ck-1-ck-2q-c1]

Although it appears that we want to invert qI-A, we actually only want to work out (qI-A)-1u0, where

u0=[001]

which means that we want to solve the system

[q-1000q-10000-1-ck-ck-1-ck-2q-c1][x1x2x3xk]=[0001]

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

qxj-xj+1=0

and thus xj+1=qxj=qjx1.

The final equation reads:

-ckx1-ck-1x2-ck-2x3-+(q-c1)xk=1

substituting in, we get:

-ckx1-ck-1qx1-ck-2q2x1--c1qk-1x1+qkx1=1

whence

x1=1qk-c1qk-1-ck-2q2-ck-1q-ck

Note that tk-c1tk-1-ck-2t2-ck-1t-ck is the characteristic polynomial of A.

Now the first component of q-n-1Anu0 is q-n-1an and so

q-n-1an=1qk-c1qk-1-ck-2q2-ck-1q-ck

Note that this is only valid if q is bigger in magnitude than any of the roots of tk-c1tk-1--ck-1.

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

bn+1=bn+bn-1+bn-2

Starting at b0=0, b1=0, b2=0, the first terms of this sequence are:

0,0,1,1,2,4,7,13,24,44,

The matrix in that case is:

[010001111]

and the characteristic polynomial of this is

c(t)=t3-t2-t-1

hence:

q-n-1bn=1q3-q2-q-1

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

10-n-1bn=11000-100-10-1=1889,2-n-1bn=1.