O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 10

Solving Linear Recurrence Relations: The Binet Form for Fn

Up to this point, if we wanted to know a specific Fibonacci number—for instance, F37—we had to start with F0 = 0, F1 = 1, and use the recurrence relation Fn = Fn−1 + Fn−2, n ≥ 2, to compute

img

Now our objective is to somehow determine F37, but without performing any of these 36 calculations. To do so, we want to derive an explicit formula for the general term Fn in terms of n—not in terms of previous values in the sequence of Fibonacci numbers. We shall accomplish this by introducing the following idea:

Definition 10.1: For real constants C0, C1, C2, . . ., Ck, with C0 ≠ 0 and Ck ≠ 0, an expression of the form

img

where nk, is called a kth-order linear homogeneous recurrence relation with 53 constant coefficients. When the right side of this recurrence relation is not 0, then the relation is referred to as nonhomogeneous.

We shall focus our concern on the case where k = 2, C0 = 1, and C2 ≠ 0. For example,

img

or

img

is a second-order linear homogeneous recurrence relation with constant coefficients.

To solve such a recurrence ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required