Blog

# Fibonacci, Lucas and Pell sequences

Even more stuff that I stumbled across while thinking about the Fibonacci sequence while trying to get into the right frame of mind to think about harder things.

Suppose that we have a recursion defined by

f(n + 2) = A f(n + 1) + B f(n)

We can write this as

f(n) = α an + β bn

where

a = (A + √(A2 + 4 B) / 2

and

b = (A – √(A2 + 4 B) / 2

If we have that

f(0) = 0

and

f(1) = 1

like with we do with the Fibonacci sequence, then we find that

α = 1 / (ab)

and

β = -1 / (ab)

so that

f(n) = (anbn) / (ab)

Suppose that we want to get other interesting forms of f(n) like where

α = 1

and

β = 1

so that

f(n) = an + bn

It’s easy to show that we can get this when

f(0) = 2

and

f(1) = A

which gives what’s called the Lucas sequence when A = 1.

It’s also easy to show that if we want to make sure that we have

f(n) = (an + bn) / (a + b)

then we need to have

f(0) = 2 / A

and

f(1) = 1

If we want to have integer values, making A = 2 is a reasonable way to try to do this. This gives us the Pell sequence, which is defined by the recursion

f(n + 2) = 2 f(n + 1) + f(n)

Finally, that if we want to make sure that we have

f(n) = anbn

or

α = 1

and

β = -1

then we find that we get this when

f(0) = 0

and

f(1) = ab = √(A2 + 4B)

We can get this to be an integer, for example, if we have that

A = 3

and

B = 4

or from the recursion

f(n + 2) = 3 f(n + 1) + 4 f(n)

with

f(1) = 5

That seems to cover the interesting cases, or at least the ones that I had time to think about today.

In any event, this might give us some idea of how Lucas and Pell came to think about the sequences that now carry their names.