THE ASYMPTOTIC BEHAVIOR OF THE GOLDEN NUMBERS

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

In [2] the “Golden polynomials”

G_{n+2}(x) = xG_{n+1}(x) + G_{n}(x), G_{0}(x) = −1, G_{1}(x) = x − 1

and their maximal real root g_{n} (the “golden numbers”) were investigated. It was observed that, as n → ∞, g_{n} → \frac{3}{2}; furthermore it was suggested there might be a more precise formula, since numerical experiments seemed to indicate a dependency on the parity of n of the lower order terms.

This open question will be solved in the present paper.

Solving the recursion for the Golden polynomials by standard methods we get the explicit formula

G_{n}(x) = Aλ^{n} + Bμ^{n},

with

λ = \frac{x + \sqrt{x^{2} + 4}}{2}, μ = \frac{x − \sqrt{x^{2} + 4}}{2},

A = \frac{1}{2\sqrt{x^{2} + 4}} (3x − 2 − \sqrt{x^{2} + 4} ) , B = −\frac{1}{2\sqrt{x^{2} + 4}} (3x − 2 + \sqrt{x^{2} + 4} ) .

Everything is much nicer when we substitute

x = u − \frac{1}{u} .

G_{n}(x) = 0 can be rephrased as −B/A = (λ/μ)^{n}, or

\frac{(2u + 1)(u − 1)}{(u + 1)(u − 2)} = (−u^{2})^{n} .

Now it is plain to see that, for large n, this equation can only hold if u is either close to 2 or to u = −\frac{1}{2}. In both cases, this would mean x is close to \frac{3}{2}. Let us assume that u is close to 2. It is clear that the cases when n is even or odd have to be distinguished. We start with n = 2m and rewrite the equation as

u − 2 = \frac{(2u + 1)(u − 1)}{(u + 1)}u^{−4m}.

We get the asymptotic behavior of the desired solution by a process known as “bootstrapping” which is explained int [1]. First, we set u = 2 + δ, insert u = 2 into the right hand side, and get an approximation for δ. Then we insert u = 2 + δ into the right hand side, expand, and get the next term. This procedure can be repeated to get as many terms as needed. In this way, we get

δ ∼ \frac{5}{3} · 16^{−m},

and with u = 2 + \frac{5}{3} · 16^{−m} + ε, we find

ε ∼ −\frac{25}{6}m · 256^{−m}.

From

u ∼ 2 + \frac{5}{3} · 16^{−m} − \frac{25}{6}m · 256^{−m}

we find by substitution

x ∼ \frac{3}{2} + \frac{25}{12}16^{−m} − \frac{125}{24}m256^{−m}.

Now let us consider the case n is odd, n = 2m + 1. Then our equation is

u − 2 = −\frac{(2u + 1)(u − 1)}{(u + 1)u^{2}}u^{−4m},

and we find as above

u ∼ 2 − \frac{5}{12}16^{−m} − \frac{25}{72}m256^{−m},

and also

x ∼ \frac{3}{2} − \frac{25}{48}16^{−m} − \frac{125}{288}m256^{−m}.

Confining ourselves to two terms we write our findings in a single formula as

g_{n} ∼ \frac{3}{2} + (−1)^{n} \frac{25}{12}4^{−n},

which matches perfectly with the empirical data from [2].

References

1. D.Greene, D.Knuth, Mathematics for the Analysis of Algorithms, Birkhäuser, 1981.

2. G.Moore, The limit of the golden numbers is 3/2, The Fibonacci Quarterly 32 (1994), 211–217.

AMS classification: 11B39, 11B37, 11C08

TU Vienna Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: proding@email.tuwien.ac.at