## You are here

Homeapproximating algebraic numbers with linear recurrences

## Primary tabs

# approximating algebraic numbers with linear recurrences

Linear recurrences can be used to obtain rational approximations for real algebraic 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}$ and further assume that the roots of $p$ are distinct and that all the other 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 recurrence is

$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 conditions of the recurrence. If $b_{1}\neq 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}\over b_{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 what we 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 approximate the 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 roots of a polynomial using this technique. A way to do this is to start with a rational number $h$ which is closer to the desired root than to 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, we guess that the roots are close to $0$, $+3i$, and $-3i$. Since the two 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, this recursion 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, this recursion gives us the sequence

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

## Mathematics Subject Classification

11B37*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections