%Fibonacci Quarterly


\input amstex
\documentstyle{amsppt}

\magnification=\magstep1


\headline=               
{\ifnum\pageno=1\hfil
 \else
 \hfil{\tenrm\number\pageno}\hfil
\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13
\TagsOnRight
%\NoBlackBoxes
\hfuzz=10pt

\topmatter
\title
the asymptotic behavior of the golden numbers
\endtitle

\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address 
{\rm \flushpar AMS classification: 11B39, 11B37, 11C08}\newline
\bigskip\flushpar
TU Vienna
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress 
\email proding\@email.tuwien.ac.at
\endemail







\endtopmatter
\document

In \cite{2} the ``Golden polynomials''
$$
G_{n+2}(x)=xG_{n+1}(x)+G_n(x),\qquad 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\to\infty$, $g_n\to \frac32$; 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.
\medskip

Solving the recursion for the Golden polynomials by
standard methods we get the explicit formula
$$
G_n(x)=A\lambda^n+B\mu^n, 
$$
with
$$\gather
\lambda=\frac{x+\sqrt{x^2+4}}{2}, \quad
\mu=\frac{x-\sqrt{x^2+4}}{2},\\
A=\frac1{2\sqrt{x^2+4}}\left(3x-2-\sqrt{x^2+4}\, \right), \quad
B=-\frac1{2\sqrt{x^2+4}}\left(3x-2+\sqrt{x^2+4}\, \right).
\endgather
$$
Everything is much nicer when we substitute
$$
x=u-\frac1u\ .
$$
$G_n(x)=0$ can be rephrased as $-B/A=(\lambda/\mu)^n$, or
$$
\frac{(2u+1)(u-1)}{(u+1)(u-2)}=\left(-u^2\right)^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=-\frac12$.
In both cases, this would mean $x$ is
close to $\frac32$. 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 \cite{1}.
First,
we set $u=2+\delta$, insert $u=2$ into the right hand side, and
get an approximation for $\delta$. Then we insert $u=2+\delta$ 
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
$$
\delta\sim\frac53\cdot16^{-m},
$$
and with $u=2+\frac53\cdot16^{-m}+\varepsilon$, we find
$$
\varepsilon\sim-\frac{25}6m\cdot256^{-m}.
$$
From 
$$
u\sim 2+\frac53\cdot16^{-m}-\frac{25}6m\cdot256^{-m}
$$
we find by substitution
$$
x\sim \frac32+\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\sim 2-\frac{5}{12}16^{-m}-\frac{25}{72}m256^{-m},
$$
and also
$$
x\sim \frac32-\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\sim\frac32+(-1)^n\frac{25}{12}4^{-n},
$$
which matches perfectly with the empirical data from \cite{2}.














\Refs
\ref \no 1\by D.Greene, D.Knuth\book Mathematics for the 
        Analysis of Algorithms \yr 1981 \publ Birkh\"auser \endref
\ref \no2 \by G.Moore\paper The limit of the golden numbers is {\rm 3/2}
\jour The Fibonacci Quarterly \pages 211--217\vol32\yr1994
\endref
\endRefs

\enddocument
