2007-10-01

Fibonacci's Rabbits

EWD797, "Fibonacci numbers and Leonardo numbers" begins with a disclaimer: The following formal derivations and computations are absolutely elementary and without scientific interest. It uses, however, a simple method to resolve the generating function (used again in EWD801) which is less general than the one explained in Concrete Mathematics or in generatingfunctionology (highly recommended, by the way) but very easy to use.

It then goes on to mention Leonardo numbers:

L.0 = L.1 = 1
L.n = L.(n-1) + L.(n-2) + 1

and explaining that, since the recurrence is not homogeneous, said method cannot be applied.

It then proceeds to pull off a rabbit out of the hat, by rewriting:

(0)   (L.n + 1) = (L.(n-1) + 1) + (L.(n-2) + 1)

This trick is quite nifty and not too subtle; what follows, however, is rather flashy: and we immediately derive:

L.n = 2·F.n - 1

Maybe I'm dense and the immediacy of the derivation is staring me in the face; I cannot justify the identity, other than by saying that yes, by induction it is true. So here is what I think.

First, I can tell that (0) is implied by

(1)   L.n = F.n - 1

This, however, fails for L.0 and L.1. What is then the simplest adjustment I can perform on (1) that satisfies the base? Well, since F.n = F.(n - 1) + F.(n - 2), I can multiply through a constant, call it k:

k·F.n = k·F.(n - 1) + k·F.(n - 2)

and equate with (0) to get L.n = k·F.n - 1. By solving the base case, we have that L.0 = k·F.0 - 1 forces k = 2.

This I don't find immediate.

No comments: