Chapter 4

Properties of the Fibonacci Numbers

As we examine the entries in Table 3.1, we find that the greatest common divisor of F5 = 5 and F6 = 8 is 1. This is due to the fact that the only positive integers that divide F5 = 5 are 1 and 5, and the only positive integers that divide F6 = 8 are 1, 2, 4, and 8. We shall denote this by writing gcd (F5, F6) = 1. Likewise, gcd (F9, F10) = 1, since 1, 2, 17, and 34 are the only positive integers that divide F9 = 34, while the only positive integers that divide F10 = 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 (Fn, Fn+1) = 1.

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

equation

So if d divides Fr and Fr+1, it follows that d divides 9 Fr−1. This then contradicts gcd (Fr−1, Fr) = 1. Consequently, gcd (Fn, Fn+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 (Fn, Fn+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 ...

Get Fibonacci and Catalan Numbers: An Introduction now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.