FT9: de Moivre's Formula

In this section, we look at the analogue to de Moivre's formula, cos kx + i sin kx = (cos x + i sin x)^k.

Let n be any integer. We know that L(n) + √5 F(n) = 2 φⁿ.

It follows that, for any non-negative integer k:

• L(kn) + √5 F(kn) = (L(n) + √5 F(n))^k / 2^k—1

If k is positive, we can expand this using the binomial theorem. Then, applying 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, we can derive the following two formulas:

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

Note: [x] here denotes the greatest integer less than or equal to x.

However, the factor 2^k—1 here gets in the way, and we'll come up with more useful versions of these formulas in the next section.