Constructing a recursive sequence that converges to sqrt 17

Question

One of the problems that we have for abstract math is the following: Using the recursive sequence definition, construct a sequence that converges to $\sqrt{17}$. It is my understanding that the recursive sequence definition is: $F_n=F_{n-1}+F_{n-2}$. I also found that $\sqrt{17}$ is a root of the quadratic equation: $x^2-2x-16=0$. Now I don't know how to go about constructing the sequence to converge to $\sqrt{17}$. Anyone know a good way to go about this? Any help is greatly appreciated!

Answer 1

Here's a slightly cheeky way:

let $F_n=2F_{n-1}-F_{n-2}$ and $F_0=F_1=\sqrt{17}$.

Then the sequence is identically $\sqrt{17}$ the whole time, hence it converges to $\sqrt{17}$.

Answer 2

Sequences defined recursively like $F_n=aF_{n-1}+bF_{n-2}$ generally don’t converge unless the initial conditions force them to be constant. (A recursive sequence converging to $\sqrt{17}$ is $a_1=\sqrt{17}$, $a_{i+1}=a_i$, but that’s not likely what you want.)

A better approach might be to use Newton’s method to approximate a root of $x^2-17$. Start with a value close to a solution, say $x_1=4$. The point $(x_1,x_1^2-17)$ is on the graph of $y=x^2-17$, but $x_1$ is not $\sqrt{17}$, since $x_1^2-17=-1$, not $0$. Take as the next approximation, $x_2$, the intersection of the tangent line when $x=x_1$ with the $x$-axis. In general, the tangent line at $(x_i,x_i^2-17)$ has slope $\frac{d}{dx}(x_i^2-17)=2x_i$, so the one through $(x_i,x_i^2-17)$ has slope $2x_i$. To find its intersection with the $x$-axis, you want to decrease $y$ (possibly by a negative amount) from $x_i^2-17$ to $0$ along the line, which has slope $2x_i$, so you need to decrease $x_i$ by $\frac{x_i^2-17}{2x_i}$. This leads to the recursive sequence $$x_1=4\mbox{ and }x_{i+1} = \frac{x_i}{2}-\frac{17}{2x_i}.$$ Newton’s method doesn’t always converge, and it doesn’t always converge to the root closest to the starting point, but for a quadratic equation and a starting point that’s not the vertex of the parabola (where the tangent line is not horizontal), it will.

Answer 3

$$ F_n = {F_{n-1} + 17/F_{n-1} \over 2} $$

where $F_0 > 0$, is what I use, when i need one.. it's basically the same as Steve wrote. Besides, the way I understand it a recursive definition is simply $F_n = f(F_{n-m})$ for some $m \in \mathbb{N}$, ie. basically any function that takes an old value to produce the new one.