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 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 ...

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