FT11: Fibonacci-Based Formulas for F(kn+m) and L(kn+m)

In the last section, we derived the following form of our analogue to de Moivre's theorem:

• F(kn−1) + φ F(kn) = (F(n−1) + φ F(n))^k

Expanding the expression on the right with the binomial formula, applying the equation φ ^j = F( j − 1 ) + φ F ( j ), and then using 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, one obtains the following two formulas:

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

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

• F (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) F ( j + m ) F(n) ^j F(n−1)^k−j

Using the fact that L(x) = F(x−1) + F(x+1), we can also see that:

• L (kn + m) = ∑_{0 ≤ j ≤ k} (  k   j  ) L ( j + m ) F(n) ^j F(n−1)^k−j