Blog

# More patterns in the Fibonacci and Lucas sequences

More observations about the Fibonacci and Lucas sequences.

As before, suppose that we have a second-order linear recursion given by

xn+2 = A xn+1 + B xn

and we write

x2A xB = (xa) (xb)

where

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

and

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

For a Fibonacci-like sequence we have that

f(n) = (anbn) / (a b)

and for a Lucas-like sequence we have that

g(n) = an + bn

Now if we look at

(a + b)n = an + … + bn

we see that all but the first and last terms are divisible by ab so that

(a + b)nan + bn (mod ab)

We can write

x2A xB = (xa) (xb)

= x2 – (a + b) x + ab

so that

A = – (a + b)

and

B = ab

This means that we can write

g(n) = an + bn

≡ (a + b)n (mod ab)

Or that

g(n) ≡ An (mod B)

which looks like an interesting relationship.

Similarly, we can write

f(n) = (anbn) / (a b)

= an-1 + … + bn-1

an-1 + bn-1 (mod ab)

g(n – 1) (mod ab)

An-1 (mod B)

or that

f(n) ≡ An-1(mod B)

which also seems to be an interesting relationship.