## Lucas Sequences

### October 1, 2013

We studied Fibonacci numbers in a previous exercise. In today’s exercise, we will look at a generalization of Fibonacci numbers called Lucas numbers, which were studied by Edouard Lucas in the late 1800s.

Recall that each Fibonacci number is the sum of the two previous Fibonacci numbers, with the first two being 1 and 1; thus, the Fibonacci numbers begin 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …. The definition of the Lucas numbers is similar, but the first two Lucas numbers are 1 and 3; thus, the Lucas numbers begin 1, 3, 4, 7, 11, 18, 29, 47, 76, …, and they grow faster than the Fibonacci numbers.

Lucas went on to generalize the Fibonacci numbers even further. He define two sequences *U _{n}*(

*P*,

*Q*) and

*V*(

_{n}*P*,

*Q*) as follows: Start with integer

*P*and

*Q*satisfying

*D*=

*P*

^{2}− 4

*Q*> 0. Then, by the quadratic formula, the roots of

*x*

^{2}−

*P x*+

*Q*= 0 are

*a*= (

*P*+ sqrt(

*D*)) / 2 and

*b*= (

*P*− sqrt(

*D*)) / 2. Then

*U*(

_{n}*p*,

*q*) = (

*a*−

^{n}*a*) / (

^{n}*a*−

*b*) and

*V*(

_{n}*P*,

*Q*) =

*a*+

^{n}*a*.

^{n}Now the Fibonacci and Lucas numbers are just special cases of the *U* and *V* sequences: the Fibonacci numbers are *U _{n}*(1, -1) and the Lucas numbers are

*V*(1, -1).

_{n}It is easy to compute a particular*U* or *V* sequence. The formulas are similar to the method of computing the Fibonacci sequence: *U _{m}*(

*P*,

*Q*) =

*P U*

_{m−1}(

*P*,

*Q*) −

*Q U*

_{m−2}(

*P*,

*Q*) and

*V*(

_{m}*P*,

*Q*) =

*P V*

_{m−1}(

*P*,

*Q*) −

*Q V*

_{m−2}(

*P*,

*Q*).

It is also easy to calculate a particular *U* or *V* in the sequence using a chain that takes only logarithmic time based on the following identities: *U*_{2n} = *U _{n} U_{n}*,

*U*

_{2n+1}=

*U*

_{n+1}

*V*−

_{n}*Q*,

^{n}*V*

_{2n}=

*V*

_{n}^{2}− 2

*Q*, and

^{n}*V*

_{2n+1}=

*V*

_{n+1}

*V*−

_{n}*P Q*.

^{n}You can see all of these formulas at MathWorld. Our interest in Lucas sequences isn’t merely academic; we’ll see an application of Lucas sequences in a future exercise.

Your task is to write programs that compute the *U* and *V* sequences and that compute any given element of either of the two sequences. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.