A periodic recurrence relation is one containing a cycle of infinitely repeating elements.

Periodic Recurrence Relations

The Golden Recurrence Relation

The following recurrence relation has a cycle length of 5:

u₂ = 1/(u₀ u₁^f)

f² - 1 = f   and
f² - f = 1 

In terms of u₀ and u₁, I will calculate the next four elements of the sequence, to show that the u₅ = u₀.

u₂ = u₀^-1 u₁^-f
u₃ = u₁^-1 u₂^-f = u₁^-1 (u₀^-1 u₁^-f)^-f = u₀^f u₁^f²-1 = u₀^f u₁^f
u₄ = u₂^-1 u₃^-f = (u₀^-1 u₁^-f)^-1 (u₀^f u₁^f)^-f = u₀^1-f² u₁^f-f² = u₀^-f u₁^-1
u₅ = u₃^-1 u₄^-f = (u₀^f u₁^f)^-1 (u₀^-f u₁^-1)^-f = u₀^-f+f² u₁^-f+f = u₀

5-cycle Relation

u₂ = (u₁+1)/u₀  is a 5-cycle relation

Here's the proof:

c = (b+1)/a
d = (c+1)/b = ((b+1)/a+1)/b = (a+b+1)/(ab)
e = (d+1)/c = (((a+b+1)/(ab))+1)/((b+1)/a) = (a+1)/b
f = (e+1)/d = (((a+1)/b)+1)/((a+b+1)/(ab)) = a

6-cycle Relation

u₂ = u₁/u₀ is a 5-cycle relation

Here's the proof:

c = b/a
d = c/b = (b/a)/b = 1/a
e = d/c = (1/a)/(b/a) = 1/b
f = e/d = (1/b)/(1/a) = a/b
g = f/e = (a/b)/(1/b) = a

Internet References

Mathworld -- Golden Ratio

Related pages in this website

Linear Recurrence Relation -- a closed form solution

Fibonacci Numbers -- whose successive ratios approach the Golden Ratio

Trig functions of Special Angles -- The golden ratio pops up here, too.

Formal Power Series

Generating Function

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]