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 13

The Lucas Numbers: Further Properties and Examples

At this point we have seen many examples where the Fibonacci numbers arise—and there are still more to come. In addition, in the text and, especially, in the exercises, we found that there are numerous properties that this number sequence exhibits. The Lucas numbers likewise exhibit many interesting properties. In fact, now that we are aware of both of these number sequences, we find that there are some properties interrelating the two sequences. Our next example will provide some of these properties. Many more appear in the exercises for this chapter.

Example 13.1: Previously, in Example 12.5, we let in count the number of independent sets of vertices for a path on n vertices and cn the number of independent sets of vertices for a cycle on n vertices. In that example we learned that

img

Since cn turned out to be the Lucas number Ln and in = Fn+2, this result translates into the following:

Property 13.1:

img

And from this the next property follows.

Property 13.2:

img

This second property can be used to provide additional examples where the Lucas numbers arise:

i. In Example 6.2 we learned that the number of compositions of n, where ...

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