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 3

The Recursive Definition

Upon examining the sequence in the middle column of Table 3.1, we see that after the first two entries, each entry is the sum of the two preceding entries. For example, 1 = 1 + 0, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2, 8 = 5 + 3, . . ., 55 = 34 + 21. So we are able to determine later numbers in the sequence when we know the values of earlier numbers in the sequence. This property now allows us to define what we shall henceforth consider to be the Fibonacci numbers. Consequently, the sequence of Fibonacci numbers is defined, recursively, as follows:

Table 3.1

img

For n ≥ 0, if we let Fn denote the nth Fibonacci number, we have

1. F0 = 0, F1 = 1            (The Initial Conditions)

2. Fn = Fn−1 + Fn−2, n ≥ 2 (The Recurrence Relation)

Therefore, the sequence F0, F1, F2, F3, . . ., which appears in the middle column of Table 3.1, now has a different starting point, namely, F0, from the sequence F1, F2, F3, . . ., which appears in the third column of Table 3.1. This sequence—F0, F1, F2, F3, . . .—is now accepted as the standard definition for the sequence of Fibonacci numbers. It is one of the earliest examples of a recursive sequence in mathematics. Many feel that Fibonacci was undoubtedly aware of the recursive nature of these numbers. However, it was not until 1634, when mathematical notation had 9 sufficiently progressed, that the Dutch mathematician Albert ...

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