\(% Differentiation % https://tex.stackexchange.com/a/60546/ \newcommand{\Diff}{\mathop{}\!\mathrm{d}} \newcommand{\DiffFrac}[2]{\frac{\Diff #1}{\Diff #2}} \newcommand{\DiffOp}[1]{\frac{\Diff}{\Diff #1}} \newcommand{\Ndiff}[1]{\mathop{}\!\mathrm{d}^{#1}} \newcommand{\NdiffFrac}[3]{\frac{\Ndiff{#1} #2}{\Diff {#3}^{#1}}} \newcommand{\NdiffOp}[2]{\frac{\Ndiff{#1}}{\Diff {#2}^{#1}}} % Evaluation \newcommand{\LEvalAt}[2]{\left.#1\right\vert_{#2}} \newcommand{\SqEvalAt}[2]{\left[#1\right]_{#2}} % Epsilon & Phi \renewcommand{\epsilon}{\varepsilon} \renewcommand{\phi}{\varphi} % Sets \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\PP}{\mathbb{P}} \renewcommand{\emptyset}{\varnothing} % Probabililty \DeclareMathOperator{\Cov}{Cov} \DeclareMathOperator{\Corr}{Corr} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\Expt}{E} \DeclareMathOperator{\Prob}{P} % Distribution \DeclareMathOperator{\Binomial}{B} \DeclareMathOperator{\Poisson}{Po} \DeclareMathOperator{\Normal}{N} \DeclareMathOperator{\Exponential}{Exp} \DeclareMathOperator{\Geometric}{Geo} \DeclareMathOperator{\Uniform}{U} % Complex Numbers \DeclareMathOperator{\im}{Im} \DeclareMathOperator{\re}{Re} % Missing Trigonometric & Hyperbolic functions \DeclareMathOperator{\arccot}{arccot} \DeclareMathOperator{\arcsec}{arcsec} \DeclareMathOperator{\arccsc}{arccsc} \DeclareMathOperator{\sech}{sech} \DeclareMathOperator{\csch}{csch} \DeclareMathOperator{\arsinh}{arsinh} \DeclareMathOperator{\arcosh}{arcosh} \DeclareMathOperator{\artanh}{artanh} \DeclareMathOperator{\arcoth}{arcoth} \DeclareMathOperator{\arsech}{arsech} \DeclareMathOperator{\arcsch}{arcsch} % UK Notation \DeclareMathOperator{\cosec}{cosec} \DeclareMathOperator{\arccosec}{arccosec} \DeclareMathOperator{\cosech}{cosech} \DeclareMathOperator{\arcosech}{arcosech} % Paired Delimiters \DeclarePairedDelimiter{\ceil}{\lceil}{\rceil} \DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor} \DeclarePairedDelimiter{\abs}{\lvert}{\rvert} \DeclarePairedDelimiter{\ang}{\langle}{\rangle} % Vectors \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\bvect}[1]{\overrightarrow{#1}} % https://tex.stackexchange.com/a/28213 % \DeclareMathSymbol{\ii}{\mathalpha}{letters}{"10} % \DeclareMathSymbol{\jj}{\mathalpha}{letters}{"11} % \newcommand{\ihat}{\vect{\hat{\ii}}} % \newcommand{\jhat}{\vect{\hat{\jj}}} \newcommand{\ihat}{\textbf{\^{ı}}} \newcommand{\jhat}{\textbf{\^{ȷ}}} \newcommand{\khat}{\vect{\hat{k}}} % Other Functions \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\tr}{tr} % Other Math Symbols \DeclareMathOperator{\modulo}{mod} \newcommand{\divides}{\mid} \newcommand{\notdivides}{\nmid} \newcommand{\LHS}{\text{LHS}} \newcommand{\RHS}{\text{RHS}} \newcommand{\degree}{^{\circ}}\)
By rearranging, we have \[ x_{n + 1} = 1 + \frac {1}{x_n + 1}, \] and \(x_n \geq 1\) for \(n = 0\).
If \(x_n \geq 1\) for some \(n = k \geq 0\), we must have \(\frac {1}{x_{k} + 1} > 0\), and hence \[ x_{k + 1} = 1 + \frac {1}{x_k + 1} > 1, \] and so \(x_{k + 1} \geq 1\).
Hence, by the principle of mathematical induction, \(x_n \geq 1\) for all \(n \in \NN \).
We have \begin {align*} x_{n + 1}^2 - 2 & = \left (1 + \frac {1}{x_n + 1}\right )^2 - 2 \\ & = 1 + \frac {2}{x_n + 1} + \frac {1}{\left (x_n + 1\right )^2} - 2 \\ & = \frac {1 + 2 \left (x_n + 1\right ) - \left (x_n + 1\right )^2}{\left (x_n + 1\right )^2} \\ & = \frac {1 + 2 x_n + 2 - x_n^2 - 2x_n - 1}{\left (x_n + 1\right )^2} \\ & = \frac {- x_n^2 + 2}{\left (x_n + 1\right )^2} \\ & = - \frac {x_n^2 - 2}{\left (x_n + 1\right )^2}. \end {align*}
Since \[ \frac {1}{\left (x_n + 1\right )^2} > 0, \] it must be \(x_{n + 1}^2 - 2\) and \(x_n^2 - 2\) must take opposite signs.
\begin {align*} \abs *{x_{n + 1}^2 - 2} & = \frac {1}{\left (x_n + 1\right )^2} \abs *{x_n^2 - 2} \\ & \leq \frac {1}{(1 + 1)^2} \abs *{x_n^2 - 2} \\ & = \frac {1}{4} \abs *{x_n^2 - 2}. \end {align*}
\(x_0^2 - 2 = -1 < 0\), and so \(x_n^2 - 2 < 0\) for all even \(n\), and \(> 0\) for all odd \(n\).
Hence, \(x_{10}^2 - 2 < 0\),and hence \(x_{10}^2 \leq 2\).
We have \begin {align*} \abs *{x_0^2 - 2} & = \abs *{1 - 2} = 1, \\ \abs *{x_1^2 - 2} & \leq \frac {1}{4} \abs *{x_0^2 - 2} = \frac {1}{4}, \\ & \phantom {\leq }\vdots \\ \abs *{x_n^2 - 2} & \leq \frac {1}{4^n}, \end {align*}
and hence \[ \abs *{x_10^2 - 2} \leq \frac {1}{4^{10}} = \frac {1}{2^{20}}. \]
We have \begin {align*} 2^{20} & = \left (2^{20}\right )^2 \\ & = 1024^2 \\ & > \left (10^3\right )^2 \\ & = 10^6, \end {align*}
and so \[ \abs *{x_{10}^2 - 2} = 2 - x_{10}^2 < 10^{-6}, \] and hence \[ 2 - 10^{-6} < x_{10}^2 < 2, \] which gives \[ 2 - 10^{-6} \leq x_{10}^2 \leq 2. \]
We have \begin {align*} y_{n + 1} - \sqrt {2} & = \frac {y_n^2 - 2\sqrt {2} y_n}{2 y_n} \\ & = \frac {y_n^2 - 2 \sqrt {2} y_n + \left (\sqrt {2}\right )^2}{2 y_n} \\ & = \frac {\left (y_n - \sqrt {2}\right )^2}{2 y_n}. \end {align*}
\(y_n \geq 1\) is true for the base case \(n = 0\).
If it is true for \(n = k\), we have \[ \frac {\left (y_n - \sqrt {2}\right )^2}{2 y_n} \geq 0, \] and so \(y_{n + 1} - \sqrt {2} \geq 0\), and hence \(y_{n + 1} \geq \sqrt {2} \geq 1\) as desired.
In fact, we can conclude that \(y_n \geq \sqrt {2}\) for all \(n \geq 1\).
Since \(y_n \geq 1\), we have \(0 \leq \frac {1}{y_n} \leq 1\), and hence we have \[ y_{n + 1} - \sqrt {2} \leq \frac {\left (y_n - \sqrt {2}\right )^2}{2}. \]
We aim to show the desired result by induction on \(n\). The base case when \(n = 1\) is \[ y_1 = \frac {y_0^2 + 2}{2 y_0} = \frac {1^2 + 2}{2} = \frac {3}{2}, \] and \[ \RHS = 2 \cdot \left (\frac {\sqrt {2} - 1}{2}\right )^{2 \cdot 1} = 2 \cdot \frac {2 + 1 - 2 \sqrt {2}}{4} = \frac {3}{2} - \sqrt {2}, \] and hence \[ \LHS = y_1 - \sqrt {2} = \frac {3}{2} - \sqrt {2} \leq \RHS \] as desired.
Now we assume the desired result is true for some \(n = k\). For \(n = k + 1\), \begin {align*} y_{k + 1} - \sqrt {2} & \leq \frac {\left (y_k - \sqrt {2}\right )^2}{2} \\ & \leq \frac {\left [2 \cdot \left (\frac {\sqrt {2} - 1}{2}\right )^{2^k}\right ]^2}{2} \\ & = \frac {4 \cdot \left (\frac {\sqrt {2} - 1}{2}\right )^{2^k \cdot 2}}{2} \\ & = 2 \cdot \left (\frac {\sqrt {2} - 1}{2}\right )^{2^{k + 1}}, \end {align*}
which is precisely the desired statement for \(n = k + 1\).
So the desired is true for the base case where \(n = 1\). Given it is true for some \(n = k\), it is true for \(n = k + 1\). Hence, by the principle of mathematical induction, \[ y_n - \sqrt {2} \leq 2 \cdot \left (\frac {\sqrt {2} - 1}{2}\right )^{2^n} \] for all \(n \geq 1\).
First, we have \(y_{10} \geq \sqrt {2}\) by the stronger bound found for the first part.
Additionally, \begin {align*} y_{10} - \sqrt {2} & \leq 2 \cdot \left (\frac {\sqrt {2} - 1}{2}\right )^{2^{10}} \\ & \leq 2 \cdot \left (\frac {\frac {1}{2}}{2}\right )^{2^{10}} \\ & = 2 \cdot \left (\frac {1}{2^2}\right )^{2^{10}} \\ & = 2 \cdot \left (\frac {1}{2}\right )^{2^{10} \cdot 2} \\ & = \frac {2}{2^{2^{11}}} \\ & = \frac {1}{2^{2^{11} - 1}}. \end {align*}
For the bound, notice that \begin {align*} \frac {1}{2^{2^{11} - 1}} & = \frac {1}{2^{2048 - 1}} \\ & = \frac {1}{2^{2047}} \\ & < \frac {1}{2^{2040}} \\ & = \frac {1}{\left (2^{10}\right )^{204}} \\ & < \frac {1}{\left (10^{3}\right )^{204}} \\ & < \frac {1}{\left (10^{3}\right )^{200}} \\ & = \frac {1}{10^{600}}, \end {align*}
and so \[ y_{10} \leq \sqrt {2} + 10^{-600}. \]
Hence, we can conclude \[ \sqrt {2} \leq y_{10} \leq \sqrt {2} + 10^{-600} \] as desired.