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.
 28 December, 2013 
 Algorithm, Math Problems, Python 
 Tags :
 2 Comments
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.
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(k1) + c(k2) 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 vectorspace in which inhabits, we can define a transformation (that I will call the rightshift 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 matrixvalued 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

AM

Phailure
