FT12: Lucas-Based Formulas for F(kn+m) and L(kn+m)

Let's follow the method of the last section, but using the formula

• (L(kn−1) + φL(kn))/√5 = (L(n−1) + φL(n))^k/√5^k

with Lucas numbers, instead of the similar formula with Fibonacci numbers).

Using the binomial formula and the equation φ ^j = (L( j − 1 ) + φ L ( j )) / √5, we get:

• 5^k/2 (L(kn−1) + φ L(kn))

  = √5 (L(n−1) + φ L(n))^k

  = ∑_{0 ≤ j ≤ k} (  k   j  ) √5 φ ^j L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) (L( j−1 ) + φ L( j )) L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j−1 ) L(n) ^j L(n−1)^k−j  +
         φ ∑_{0 ≤ j ≤ k} (  k   j  ) L( j ) L(n) ^j L(n−1)^k−j

We'll need to treat this differently based on whether the number k is even or odd.

Case 1: k is even.

If k is even, then 5^k/2 is an integer. It follows that, as in part 11, we can apply the fact that a + bβ = c + dβ implies that a = c and b = d if a, b, c, and d are rational and β is irrational, to conclude that the following two formulas must be true:

• 5^k/2 L (kn − 1) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j − 1 ) L(n) ^j L(n−1)^k−j, for k even
• 5^k/2 L (kn) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j ) L(n) ^j L(n−1)^k−j, for k even

Combine these two formulas with the basic recurrence relation for the Lucas numbers to yield:

• 5^k/2 L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

Also, the formula F(x) = (L(x−1) + L(x+1)) / 5 gives us:

• 5^k/2 F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) L(n) ^j L(n−1)^k−j, for k even.

Case 2: k is odd.

If k is odd, then 5^k/2 is an integer multiple of √5, so it is irrational.

We'll start with the formula 5^k/2 (L(kn−1) + φ L(kn)) = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j−1 ) L(n) ^j L(n−1)^k−j +
φ ∑_{0 ≤ j ≤ k} (  k   j  ) L( j ) L(n) ^j L(n−1)^k−j, from right before we split into two cases.

Multiply by 2φ−1 = √5 and use the fact that φ √5 = φ + 2 to yield:

• 5^(k+1)/2 (L(kn−1) + φ L(kn))

  = (2φ−1) ∑_{0 ≤ j ≤ k} (  k   j  ) L( j−1 ) L(n) ^j L(n−1)^k−j  +
         (φ+2) ∑_{0 ≤ j ≤ k} (  k   j  ) L( j ) L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) (2 L( j ) − L( j−1 )) L(n) ^j L(n−1)^k−j  +
   φ ∑_{0 ≤ j ≤ k} (  k   j  ) (2 L( j−1 ) + L( j ) )L(n) ^j L(n−1)^k−j

  = ∑_{0 ≤ j ≤ k} (  k   j  ) 5 F( j−1 ) L(n) ^j L(n−1)^k−j  +
         φ ∑_{0 ≤ j ≤ k} (  k   j  ) 5 F( j ) L(n) ^j L(n−1)^k−j

Since we're assuming that k is odd, 5^(k+1)/2 is an integer, and, dividing by 5, it follows that:

• 5^(k−1)/2 L(kn−1)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j−1 ) L(n) ^j L(n−1)^k−j

and

• 5^(k−1)/2 L(kn)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j ) L(n) ^j L(n−1)^k−j.

We can apply the recurrence relations for F and L to conclude that:

• 5^(k−1)/2 L(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) F( j+m ) L(n) ^j L(n−1)^k−j,
  for k odd.

Finally, using the facts that 5F(x) = L(x−1) + L(x+1) and L(x) = F(x−1) + F(x+1), we have:

• 5^(k+1)/2 F(kn+m)
  = ∑_{0 ≤ j ≤ k} (  k   j  ) L( j+m ) L(n) ^j L(n−1)^k−j,
  for k odd.