approximating algebraic numbers with linear recurrences

Linear recurrences can be used to obtain rational approximations for realalgebraic numbers. Suppose that $\\rho$ is the root of a polynomial $p(x)=\\sum_{k=0}^{n}c_{k}x^{k}$ with rational coefficients $c_{k}$ andfurther assume that the roots of $p$ are distinct and that all theother roots of $p$ are strictly smaller in absolute value than $\\rho$ .

Consider the recursion

\\sum_{k=0}^{n}c_{k}a_{m+k}=0.

As discussed in the parent entry, the solution of this recurrenceis

a_{m}=\\sum_{k=1}^{n}b_{k}r_{k}^{m},

where $r_{1},\\ldots,r_{n}$ are the roots of $p$ — let us agree that $r_{1}=\\rho$ — and the $b_{k}$ ’s are determined by the initial conditionsof the recurrence. If $b_{1}\eq 0$ , we have

{a_{m+1}\\over a_{m}}={b_{1}\\rho^{m+1}+\\sum_{k=2}^{n}b_{k}r_{k}^{m+1}\\over b_{1%}\\rho^{m}+\\sum_{k=1}^{n}b_{k}r_{k}^{m}}=\\rho{1+\\sum_{k=2}^{n}\\left({b_{k}\\overb%_{1}}\\right)\\left({r_{k}\\over\\rho}\\right)^{m+1}\\over 1+\\sum_{k=2}^{n}\\left({b_%{k}\\over b_{1}}\\right)\\left({r_{k}\\over\\rho}\\right)^{m}}.

Because $|\\frac{r_{k}}{\\rho}|<1$ when $k>1$ , we have $\\lim_{m\\to\\infty}(r_{k}/\\rho)^{m}=0$ , and hence

\\lim_{m\\to\\infty}{a_{m+1}\\over a_{m}}=\\rho.

To illustrate this method, we will compute the square root of two. Now,we cannot use the equation $x^{2}-2=0$ because it has two roots, $+\\sqrt{2}$ and $-\\sqrt{2}$ , which are equal in absolute value. So whatwe shall do instead is to use the equation $(x-1)^{2}=2$ , or $x^{2}-2x-3=0$ , whose roots are $1-\\sqrt{2}$ and $1+\\sqrt{2}$ . Since $|1+\\sqrt{2}|>|1-\\sqrt{2}|$ , we can use our method to approximatethe larger of these roots, namely $1+\\sqrt{2}$ ; to approximate $\\sqrt{2}$ ,we subtract $1$ from our answer. The recursion we should use is

a_{m+2}-2a_{m+1}-a_{m}=0

or, moving terms around,

a_{m+2}=2a_{m+1}+a_{m}.

If we choose $b_{1}=-b_{2}=1/(2\\sqrt{2})$ , then we have

	$\\displaystyle a_{0}$	$\\displaystyle=b_{1}\\left(1+\\sqrt{2}\\right)^{0}+b_{2}\\left(1-\\sqrt{2}\\right)^{0%}=b_{1}+b_{2}=0$
	$\\displaystyle a_{1}$	$\\displaystyle=b_{1}\\left(1+\\sqrt{2}\\right)^{1}+b_{2}\\left(1-\\sqrt{2}\\right)^{1%}=b_{1}+b_{2}+(b_{1}-b_{2})\\sqrt{2}=1.$

Starting with these values, we obtain the following sequence:

	$\\displaystyle a_{0}$	$\\displaystyle=0$
	$\\displaystyle a_{1}$	$\\displaystyle=1$
	$\\displaystyle a_{2}$	$\\displaystyle=2$
	$\\displaystyle a_{3}$	$\\displaystyle=5$
	$\\displaystyle a_{4}$	$\\displaystyle=12$
	$\\displaystyle a_{5}$	$\\displaystyle=29$
	$\\displaystyle a_{6}$	$\\displaystyle=70$
	$\\displaystyle a_{7}$	$\\displaystyle=169$
	$\\displaystyle a_{8}$	$\\displaystyle=408$
	$\\displaystyle a_{9}$	$\\displaystyle=985$
	$\\displaystyle a_{10}$	$\\displaystyle=2738$
	$\\displaystyle a_{11}$	$\\displaystyle=5741$
	$\\displaystyle a_{12}$	$\\displaystyle=13860$

Therefore, as our approximations to $\\sqrt{2}$ , we have

1,\\frac{3}{2},\\frac{7}{5},\\frac{17}{12},\\frac{41}{29},\\frac{99}{70},\\frac{239}%{169},\\frac{577}{408},\\frac{1753}{985},\\frac{3003}{2738},\\frac{8119}{5741}.

By making suitable transformations, one can compute all the rootsof a polynomial using this technique. A way to do this is to startwith a rational number $h$ which is closer to the desired root thanto the other roots, then make a change of variable $x=1/(y+h)$ .

As an example, we shall examine the roots of $x^{3}+9x+1$ .Approximating the polynomial by leaving off the constant term, weguess that the roots are close to $0$ , $+3i$ , and $-3i$ . Since thetwo complex roots are conjugates, it suffices to find one of them.

To look for the root near $0$ , we make the change of variable $x=1/y$ to obtain $y^{3}+9y^{2}+1=0$ , which gives the recursion $a_{k+3}+9a_{k+2}+a_{k}=0$ . Picking some initial values, thisrecursion gives us the sequence

0,0,1,-9,81,-738,6723,-61236,557766,-5090401,\\ldots,

whence we obtain the approximations

-\\frac{1}{9},-\\frac{1}{9},-\\frac{81}{738},-\\frac{738}{6723},-\\frac{6723}{61236%},-\\frac{61236}{557766},-\\frac{557766}{5090401},\\ldots.

To look for the root near $3i$ , we make the change of variable $x=1/(y+3i)$ to obtain $y^{3}+(9+9i)y^{2}+(-27+54i)y+82-27i=0$ , which gives the recursion

a_{k+3}+(9+9i)a_{k+2}+(-27+54i)a_{k+1}+(82-27i)a_{k}=0.

Picking some initial values, thisrecursion gives us the sequence

0,\\,0,\\,1,\\,-9-9i,\\,27+108i,\\,-82-945i,\\,-225+11196i,\\,44415-127953i,\\ldots,