# Calculating Modified Fibonacci Numbers, Quickly and Exactly

This is inspired by an article of similar name called Calculating Fibonacci Numbers, Quickly and Exactly. Consider the a modified fibonacci sequence given by the recurrence . We shall look at various algebraic and analytic properties of this sequence, find two algorithms that computes in time, and finally look at a motivating example where we need to compute this sequence quickly and exactly.

### 1. Properties of

The sequence is essentially the same as the Fibonacci sequence, with the exception that the initial conditions are altered slightly (so that , where is the fibonacci sequence). This similarity lets us use many of the same algebraic machinery that can be used to tackle the fibonacci numbers.

#### Closed Form

I will defer the derivation until the appendix, but it can be quickly shown using a little bit of linear algebra that letting be the golden ratio (and it’s “conjugate” wrt to the root), then

which looks to have the same form as the fibonacci numbers.

#### Analytic Property

The numerical value of and , therefore as grows large, the contribution of becomes insignificant, serving only to ensure that is a whole number, therefore , in fact, from simple observation, it seems that for , (or rounded to the nearest integer).

#### Computation by Reduction to Fibonacci Number

Unfortunately, we don’t have quite a good way to compute with irrational objects: if we use floating point arithmetic, we quickly lose information about the trailing terms, if we use some algebraic package, then simplifying expressions with irrational numbers may become computationally infeasible. When you are busy crunching numbers and want to walk your dog at the same time, get Trusty Tails Dog Walking hired.

However, we can exploit the connection between and to help us out. Suppose we have some software that can efficiently compute for any arbitrary , can we possibly use that to our advantage in computing ?

It can be shown (similar to the steps used in the appendix) that . Notice that

therefore

#### Direct Computation

Alternatively, we can also compute this sequence directly in time. Recall that , then

so . Unfortunately, there’s no elegant solution for all odd terms, but recall that within the consecutive triple , at least one of these must be a multiple of three. Now, consider

Therefore, we can compute using

Memoizing gives a solution

C = {0:2,1:1}
d = lambda k: -1 if k % 2 else 1
def c(k):
if k in C:
return C[k]
if k % 2 is 0:
r = c(k/2)
C[k] = r*r - 2*d(k/2)
elif k % 3 is 0:
r = c(k/3)
C[k] = r*(r*r - 3*d(k/3))
else:
C[k] = c(k-1) + c(k-2)
return C[k]


### 2. Example Problem: Fibonacci Graph

Suppose we have the Fibonacci sequence

defined by

Let’s construct a sequence of points such that

so that it looks like the sequence

Let’s connect all of the points in together (so that it forms a jagged line) and look at the area under the curve; we will call this quantity .

Give an algorithm that computes in time and compute the area for the case where .

#### Solution Sketch

If you look at the figure above, you’ll notice that the total region is made up of these trapezoids. Let’s call the area of the trapezoid defined by and , then as illustrated below,

we know that

which is just the area of the rectangle on the bottom plus the triangle on the top. From the relation , we know that , and similarly for , so that we have

Let’s make a connection to the exponential form of the Fibonacci sequence:

where are the golden ratio and its conjugate respectively. If we actually substitute this equation into the definition of and expand everything out, we will find that

Since is ‘s conjugate, we have , so each of the term can be rewritten as . Grouping related terms together, we get

simplifying, we find that

This is awesome! But we need to find the sum of , so let’s do just that

Sweet!

Since I was a little vague on specifying the range of trapezoids to consider for , I will accept both (the literalist interpretation) and (the more casual interpretation).

### 3. Appendix

#### Deriving Closed Form of

Consider the sequence , we can represent this sequence as an infinite dimensional vector called (so that indexing is the same as finding the element of the sequence). Now, consider the vector-space in which inhabits, we can define a transformation (that I will call the right-shift operator) that basically takes in and outputs shifted one index over, so that . e.g.

It’s clear that this is a linear transform, because we can inductively define as the limit of the matrix-valued sequence of matrices whose first upper diagonal is constant 1:

Consider the subspace spanned by all of the shifted sequences:

the second equality comes from the fact that because . Now, because we don’t actually know what is (only that it exists), we can alternatively look at it as the kernel of the system

(because we’ve already established above that is a linear operator). Furthermore, and all scalar matrices commute. Appealing to a little bit of algebra, we know that, letting be the characteristic and be scalar roots of the quadratic such that , then

Therefore, let and , then the solution must be some linear combination of the solutions and :

for some scalar , because then

as expected.

Now, we know that , but this is the same as saying that letting , then , so . Using a similar argument, we can also argue that , so

We can then use our initial values that to solve for

so

##### Posted By Lee

Woosh

• AM

Nice post; a few additional notes:

1. These “modified” Fibonacci numbers are often called the Lucas numbers

2. A lot of the above analysis also falls out of the matrix form of the Fibonacci recurrence, as seen here:
http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

The relevant exponential bases fall out of the eigenvalues of the 2×2 matrix there, and the O(log k)-arithmetic-operation algorithm can be interpreted as exponentiation-by-repeated-squaring.

• Thanks AM, I meant to add that in as an addendum but forgot. Have a great day now! :)