Fibonacci and Catalan Numbers: An Introduction

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

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

1. F₀ = 0, F₁ = 1            (The Initial Conditions)

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

Therefore, the sequence F₀, F₁, F₂, F₃, . . ., which appears in the middle column of Table 3.1, now has a different starting point, namely, F₀, from the sequence F₁, F₂, F₃, . . ., which appears in the third column of Table 3.1. This sequence—F₀, F₁, F₂, F₃, . . .—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 ...