# 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},\mathrm{\dots},{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}\ne 0$, we have

$$\frac{{a}_{m+1}}{{a}_{m}}=\frac{{b}_{1}{\rho}^{m+1}+\sum _{k=2}^{n}{b}_{k}{r}_{k}^{m+1}}{{b}_{1}{\rho}^{m}+{\sum}_{k=1}^{n}{b}_{k}{r}_{k}^{m}}=\rho \frac{1+\sum _{k=2}^{n}\left(\frac{{b}_{k}}{{b}_{1}}\right){\left(\frac{{r}_{k}}{\rho}\right)}^{m+1}}{1+{\sum}_{k=2}^{n}\left(\frac{{b}_{k}}{{b}_{1}}\right){\left(\frac{{r}_{k}}{\rho}\right)}^{m}}.$$ |

Because $$ when $k>1$, we have ${lim}_{m\to \mathrm{\infty}}{({r}_{k}/\rho )}^{m}=0$, and hence

$$\underset{m\to \mathrm{\infty}}{lim}\frac{{a}_{m+1}}{{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}-2{a}_{m+1}-{a}_{m}=0$$ |

or, moving terms around,

$${a}_{m+2}=2{a}_{m+1}+{a}_{m}.$$ |

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

${a}_{0}$ | $={b}_{1}{\left(1+\sqrt{2}\right)}^{0}+{b}_{2}{\left(1-\sqrt{2}\right)}^{0}={b}_{1}+{b}_{2}=0$ | ||

${a}_{1}$ | $={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:

${a}_{0}$ | $=0$ | ||

${a}_{1}$ | $=1$ | ||

${a}_{2}$ | $=2$ | ||

${a}_{3}$ | $=5$ | ||

${a}_{4}$ | $=12$ | ||

${a}_{5}$ | $=29$ | ||

${a}_{6}$ | $=70$ | ||

${a}_{7}$ | $=169$ | ||

${a}_{8}$ | $=408$ | ||

${a}_{9}$ | $=985$ | ||

${a}_{10}$ | $=2738$ | ||

${a}_{11}$ | $=5741$ | ||

${a}_{12}$ | $=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}+9{y}^{2}+1=0$, which gives the recursion ${a}_{k+3}+9{a}_{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,\mathrm{\dots},$$ |

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},\mathrm{\dots}.$$ |

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,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1},-9-9i,\mathrm{\hspace{0.17em}27}+108i,-82-945i,-225+11196i,\mathrm{\hspace{0.17em}44415}-127953i,\mathrm{\dots},$$ |

Title | approximating algebraic numbers with linear recurrences |
---|---|

Canonical name | ApproximatingAlgebraicNumbersWithLinearRecurrences |

Date of creation | 2013-03-22 16:53:03 |

Last modified on | 2013-03-22 16:53:03 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 16 |

Author | rspuzio (6075) |

Entry type | Definition |

Classification | msc 11B37 |