Fibonacci and Catalan Numbers: An Introduction

Chapter 4

Properties of the Fibonacci Numbers

As we examine the entries in Table 3.1, we find that the greatest common divisor of F₅ = 5 and F₆ = 8 is 1. This is due to the fact that the only positive integers that divide F₅ = 5 are 1 and 5, and the only positive integers that divide F₆ = 8 are 1, 2, 4, and 8. We shall denote this by writing gcd (F₅, F₆) = 1. Likewise, gcd (F₉, F₁₀) = 1, since 1, 2, 17, and 34 are the only positive integers that divide F₉ = 34, while the only positive integers that divide F₁₀ = 55 are 1, 5, 11, and 55. Hopefully we see a pattern developing here, and this leads us to our first general property for the Fibonacci numbers.

Property 4.1: For n ≥ 0, gcd (F_n, F_n+1) = 1.

Proof: We note that gcd (F₀, F₁) = gcd (0, 1) = 1. Consequently, if the result is false, then there is a first case, say n = r > 0, where gcd (F_r, F_r+1) > 1. However, gcd (F_r−1, F_r) = 1. So there is a positive integer d such that d >1 and d divides F_r and F_r+1. But we know that

So if d divides F_r and F_r+1, it follows that d divides 9 F_r−1. This then contradicts gcd (F_r−1, F_r) = 1. Consequently, gcd (F_n, F_n+1) = 1 for n ≥ 0.

Using a similar argument and Property 4.1, the reader can establish our next result.

Property 4.2: For n ≥ 0, gcd (F_n, F_n+2) = 1.

To provide some motivation for the next property, we observe that

These results suggest the following:

Property 4.3: The sum of any ...