If x 1 = ( x 0 + 2 ) / ( x 0 + 1 ) x_1 = (x_0 + 2)/(x_0 + 1) x 1 = ( x 0 + 2 ) / ( x 0 + 1 ) 2 \sqrt{2} 2 x 0 x_0 x 0 x 1 x_1 x 1
Question
If
x 0 x_0 x 0
is any positive rational number and
x 1 = x 0 + 2 x 0 + 1 , x 2 = x 1 + 2 x 1 + 1 , x 3 = x 2 + 2 x 2 + 1 , \begin{equation*} x_1 = \frac{x_0 + 2}{x_0 + 1}, \quad x_2 = \frac{x_1 + 2}{x_1 + 1}, \quad x_3 = \frac{x_2 + 2}{x_2 + 1}, \end{equation*} x 1 = x 0 + 1 x 0 + 2 , x 2 = x 1 + 1 x 1 + 2 , x 3 = x 2 + 1 x 2 + 2 , prove that
2 \sqrt{2} 2 x 0 x_0 x 0 x 1 x_1 x 1 x 2 x_2 x 2 x 3 x_3 x 3
∣ x 1 2 − 2 ∣ < ∣ x 0 2 − 2 ∣ |x_1^2 - 2| < |x_0^2 - 2| ∣ x 1 2 − 2∣ < ∣ x 0 2 − 2∣
∣ x 2 2 − 2 ∣ < 1 9 ∣ x 0 2 − 2 ∣ |x_2^2 - 2| < \frac{1}{9} |x_0^2 - 2| ∣ x 2 2 − 2∣ < 9 1 ∣ x 0 2 − 2∣
By taking
x 0 = 7 5 x_0 = \frac{7}{5} x 0 = 5 7
, or otherwise, show that
41 29 < 2 < 99 70 , \begin{equation*} \frac{41}{29} < \sqrt{2} < \frac{99}{70}, \end{equation*} 29 41 < 2 < 70 99 , and, without using tables, show that each of 41 29 \dfrac{41}{29} 29 41 99 70 \dfrac{99}{70} 70 99 2 \sqrt{2} 2 5 × 10 − 4 5 \times 10^{-4} 5 × 1 0 − 4
Suggestion
…without using tables, show that each of 41 29 \dfrac{41}{29} 29 41 99 70 \dfrac{99}{70} 70 99 2 \sqrt{2} 2 5 × 10 − 4 5 \times 10^{-4} 5 × 1 0 − 4
Without knowing 2 \sqrt{2} 2 x n x_n x n 2 \sqrt{2} 2 x n x_n x n x n + 1 x_{n+1} x n + 1
Solution
We can reason as follows:
x n + 1 < 2 ⟺ x n + 2 x n + 1 < 2 ⟺ ( x n + 2 ) < 2 ( x n + 1 ) ⟺ ( 1 − 2 ) x n < ( 2 − 2 ) ⟺ x n > 2 − 2 2 − 1 = 2 2 − 1 2 − 1 = 2 . \begin{align*} x_{n+1} < \sqrt{2} &\iff \frac{x_n + 2}{x_n + 1} < \sqrt{2} \\ &\iff (x_n + 2) < \sqrt{2}(x_n + 1) \\ &\iff (1 - \sqrt{2})x_n < (\sqrt{2} - 2) \\ &\iff x_n > \frac{2 - \sqrt{2}}{\sqrt{2} - 1} = \sqrt{2} \frac{\sqrt{2} - 1}{\sqrt{2} - 1} = \sqrt{2}. \end{align*} x n + 1 < 2 ⟺ x n + 1 x n + 2 < 2 ⟺ ( x n + 2 ) < 2 ( x n + 1 ) ⟺ ( 1 − 2 ) x n < ( 2 − 2 ) ⟺ x n > 2 − 1 2 − 2 = 2 2 − 1 2 − 1 = 2 . Since the same argument applies with < < < > > > x n x_n x n x n + 1 x_{n+1} x n + 1 2 \sqrt{2} 2
Thus x 0 x_{0} x 0 x 1 x_1 x 1 x 2 x_{2} x 2 x 3 x_3 x 3 2 \sqrt{2} 2
We can write
∣ x 1 2 − 2 ∣ = ∣ ( x 0 + 2 x 0 + 1 ) 2 − 2 ∣ = ∣ ( x 0 + 2 ) 2 − 2 ( x 0 + 1 ) 2 ( x 0 + 1 ) 2 ∣ = ∣ x 0 2 + 4 x 0 + 4 − 2 x 0 2 − 4 x 0 − 2 ∣ ∣ x 0 + 1 ∣ 2 = ∣ 2 − x 0 2 ∣ ∣ x 0 + 1 ∣ 2 = ∣ x 0 2 − 2 ∣ ∣ x 0 + 1 ∣ 2 < ∣ x 0 2 − 2 ∣ . \begin{align*} |x_1^2 - 2| &= \left| \left( \frac{x_0 + 2}{x_0 + 1} \right)^2 - 2 \right|\\ &= \left| \frac{(x_0 + 2)^2 - 2(x_0 + 1)^2}{(x_0 + 1)^2} \right|\\ &= \frac{|x_0^2 + 4x_0 + 4 - 2x_0^2 - 4x_0 - 2|}{|x_0 + 1|^2} \\ &= \frac{|2 - x_0^2|}{|x_0 + 1|^2} \\ &= \frac{|x_0^2 - 2|}{|x_0 + 1|^2} \\ &< |x_0^2 - 2|. \end{align*} ∣ x 1 2 − 2∣ = ( x 0 + 1 x 0 + 2 ) 2 − 2 = ( x 0 + 1 ) 2 ( x 0 + 2 ) 2 − 2 ( x 0 + 1 ) 2 = ∣ x 0 + 1 ∣ 2 ∣ x 0 2 + 4 x 0 + 4 − 2 x 0 2 − 4 x 0 − 2∣ = ∣ x 0 + 1 ∣ 2 ∣2 − x 0 2 ∣ = ∣ x 0 + 1 ∣ 2 ∣ x 0 2 − 2∣ < ∣ x 0 2 − 2∣. The final inequality follows since x 0 + 1 > 1 x_0 + 1 > 1 x 0 + 1 > 1
The same method as above shows that
∣ x 2 2 − 2 ∣ = ∣ x 1 2 − 2 ∣ ∣ x 1 + 1 ∣ 2 = ∣ x 0 2 − 2 ∣ ∣ x 0 + 1 ∣ 2 ∣ x 1 + 1 ∣ 2 . \begin{equation*} |x_2^2 - 2| = \frac{|x_1^2 - 2|}{|x_1 + 1|^2} = \frac{|x_0^2 - 2|}{|x_0 + 1|^2 |x_1 + 1|^2}. \end{equation*} ∣ x 2 2 − 2∣ = ∣ x 1 + 1 ∣ 2 ∣ x 1 2 − 2∣ = ∣ x 0 + 1 ∣ 2 ∣ x 1 + 1 ∣ 2 ∣ x 0 2 − 2∣ . We can write
∣ x 1 + 1 ∣ 2 = ( x 0 + 2 x 0 + 1 + 1 ) 2 = ( x 0 + 2 + x 0 + 1 ) 2 ( x 0 + 1 ) 2 = ( 2 x 0 + 3 ) 2 ( x 0 + 1 ) 2 . \begin{equation*} |x_1 + 1|^2 = \left( \frac{x_0 + 2}{x_0 + 1} + 1 \right)^2 = \frac{(x_0 + 2 + x_0 + 1)^2}{(x_0 + 1)^2} = \frac{(2x_0 + 3)^2}{(x_0 + 1)^2}. \end{equation*} ∣ x 1 + 1 ∣ 2 = ( x 0 + 1 x 0 + 2 + 1 ) 2 = ( x 0 + 1 ) 2 ( x 0 + 2 + x 0 + 1 ) 2 = ( x 0 + 1 ) 2 ( 2 x 0 + 3 ) 2 . Hence,
∣ x 2 2 − 2 ∣ = ∣ x 0 2 − 2 ∣ ∣ x 0 + 1 ∣ 2 × ( x 0 + 1 ) 2 ( 2 x 0 + 3 ) 2 = ∣ x 0 2 − 2 ∣ ( 2 x 0 + 3 ) 2 < 1 9 ∣ x 0 2 − 2 ∣ , \begin{equation*} |x_2^2 - 2| = \frac{|x_0^2 - 2|}{|x_0 + 1|^2} \times \frac{(x_0 + 1)^2}{(2x_0 + 3)^2}= \frac{|x_0^2 - 2|}{(2x_0 + 3)^2} < \tfrac{1}{9} |x_0^2 - 2|, \end{equation*} ∣ x 2 2 − 2∣ = ∣ x 0 + 1 ∣ 2 ∣ x 0 2 − 2∣ × ( 2 x 0 + 3 ) 2 ( x 0 + 1 ) 2 = ( 2 x 0 + 3 ) 2 ∣ x 0 2 − 2∣ < 9 1 ∣ x 0 2 − 2∣ , with the inequality holding as x 0 > 0 x_0 > 0 x 0 > 0 ( 2 x 0 + 3 ) 2 > 9 (2x_0+3)^2>9 ( 2 x 0 + 3 ) 2 > 9
By taking
x 0 = 7 5 x_0 = \dfrac{7}{5} x 0 = 5 7
, or otherwise, show that
41 29 < 2 < 99 70 \begin{equation*} \frac{41}{29} < \sqrt{2} < \frac{99}{70} \end{equation*} 29 41 < 2 < 70 99 From the first part of the question, the iteration goes from one side of
2 \sqrt{2} 2
to the other, and back again, and so on. Since
x 0 = 1.4 < 2 x_0 = 1.4 < \sqrt{2} x 0 = 1.4 < 2
, we know that
2 < x 1 = x 0 + 2 x 0 + 1 = 7 + 10 7 + 5 = 17 12 \begin{equation*} \sqrt{2} < x_1 = \frac{x_0 + 2}{x_0 + 1} = \frac{7 + 10}{7 + 5} = \frac{17}{12} \end{equation*} 2 < x 1 = x 0 + 1 x 0 + 2 = 7 + 5 7 + 10 = 12 17 and that
2 > x 2 = x 1 + 2 x 1 + 1 = 17 + 24 17 + 12 = 41 29 \begin{equation*} \sqrt{2} > x_2 = \frac{x_1 + 2}{x_1 + 1} = \frac{17 + 24}{17 + 12} = \frac{41}{29} \end{equation*} 2 > x 2 = x 1 + 1 x 1 + 2 = 17 + 12 17 + 24 = 29 41 and, finally, that
2 < x 3 = x 2 + 2 x 2 + 1 = 41 + 58 41 + 29 = 99 70 . \begin{equation*} \sqrt{2} < x_3 = \frac{x_2 + 2}{x_2 + 1} = \frac{41 + 58}{41 + 29} = \frac{99}{70}. \end{equation*} 2 < x 3 = x 2 + 1 x 2 + 2 = 41 + 29 41 + 58 = 70 99 . …and, without using tables, show that each of 41 29 \dfrac{41}{29} 29 41 99 70 \dfrac{99}{70} 70 99 2 \sqrt{2} 2 5 × 10 − 4 5 \times 10^{-4} 5 × 1 0 − 4
With
x 0 = 7 5 x_0 = \dfrac{7}{5} x 0 = 5 7
, we saw that
x 2 = 41 29 x_2 = \dfrac{41}{29} x 2 = 29 41
and
x 3 = 99 70 x_3 = \dfrac{99}{70} x 3 = 70 99
. We saw from the very first part of the question that
x 2 x_2 x 2
and
x 3 x_3 x 3
lie on opposite sides of
2 \sqrt{2} 2
, and so
∣ x 2 − 2 ∣ < ∣ x 2 − x 3 ∣ = ∣ 41 29 − 99 70 ∣ = ∣ 41 × 70 − 99 × 29 2030 ∣ = 1 2030 < 5 × 10 − 4 . \begin{equation*} |x_2 - \sqrt{2}| < |x_2 - x_3| = \left| \frac{41}{29} - \frac{99}{70} \right| = \left| \frac{41 \times 70 - 99 \times 29}{2030} \right| = \frac{1}{2030} < 5 \times 10^{-4}. \end{equation*} ∣ x 2 − 2 ∣ < ∣ x 2 − x 3 ∣ = 29 41 − 70 99 = 2030 41 × 70 − 99 × 29 = 2030 1 < 5 × 1 0 − 4 . The same inequalities above also apply when x 2 x_2 x 2 x 3 x_3 x 3
Where did our initial iteration come from? We have
f ( x ) = x 2 − 2 = 0 ⟺ x 2 + x − 2 = x ⟺ x ( x + 1 ) − 2 = x ⟺ x = x + 2 x + 1 = g ( x ) . \begin{equation*} f(x) = x^2 - 2 = 0 \iff x^2 + x - 2 = x \iff x(x+1) - 2 = x \iff x = \frac{x+2}{x+1} = g(x). \end{equation*} f ( x ) = x 2 − 2 = 0 ⟺ x 2 + x − 2 = x ⟺ x ( x + 1 ) − 2 = x ⟺ x = x + 1 x + 2 = g ( x ) . Thus we have in action here the x = g ( x ) x = g(x) x = g ( x ) f ( x ) = 0 f(x) = 0 f ( x ) = 0 x = g ( x ) x = g(x) x = g ( x )