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
x2 – A x – B = (x – a) (x – b)
where
a = (1 + √(A2 + 4 B)) / 2
and
b = (1 – √(A2 + 4 B)) / 2
For a Fibonacci-like sequence we have that
f(n) = (an – bn) / (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)n ≡ an + bn (mod ab)
We can write
x2 – A x – B = (x – a) (x – b)
= 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) = (an – bn) / (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.
Comments