Proof that $x_{n+1} = 1+\frac{2}{x_n}$ is monotonally decreasing for all $n = 2k$

Question

$x_1 = 1$

$x_{n+1} = 1+ \frac{2}{x_n}$

It's obviously true for $x_2$ and $x_4$, but I'm missing where and how to use the induction hypothesis to prove that

$x_{2(k+1)} = x_{2k+2} \leq x_{2k+4} = x_{2(k+1+1)}$

Answer 1

Consider some first $x_n$ we have $x_1 = 1, x_2 = 3, x_3 = \frac{5}{3}, x_4 = \frac{11}{3}$. Then we can make a prediction that $2 < x_{2n+2} < x_{2n}$ for all $n$.

We can easily check that it's true for $n=1$ (which means $2 < x_4 < x_2$). Suppose that the claim is true for $n=k-1$, we will prove that it is also true for $n=k$.

Now observe that $x_{n+2} = 1 + \dfrac{2}{x_{n+1}} = 1 + \dfrac{2}{1+\frac{2}{x_n}} = \dfrac{3x_n+2}{x_n+2}$.

Our claim is equivalent to $2 < \dfrac{3x_{2k}+2}{x_{2k}+2} < x_{2k}$.

The left inequality is equivalent to $x_{2k} >2$ which is true by induction hypothesis.

The right inequality is equivalent to $x_{2k}^2 - x_{2k} - 2 > 0$ or $(x_{2k}+1)(x_{2k}-2)>0$ which is also true since $x_{2k}>2$.

Hence the claim is true for $n=k$ and therefore for all $n$.

Answer 2

$$x_{n+2}=1+\frac{2}{x_{n+1}}=1+\frac{2}{1+\frac{2}{x_n}} = \frac{3x_n+2}{x_n+2}$$

Now, when is $x_n\geq \frac{3x_n+2}{x_n+2}=x_{n+2}$? When:

$$x_n^2-x_n-2=(x_n-2)(x_n+1)\geq 0$$

In particular, this is true if $x_n>2$, which is true for $x_2$.

Answer 3

It's obviously true for $x_2$ and $x_4$, but I'm missing where and how to use the induction hypothesis to prove that

$x_{2(k+1)} = x_{2k+2} \leq x_{2k+4} = x_{2(k+1+1)}$

On the inductive step, you are attempting to establish $x_{2k+4} < x_{2k+2}$.

The inductive assumption is that $x_{2k+2} < x_{2k}$. So,

Start with what you are trying to prove.... $$x_{2k+4} < x_{2k+2}$$ $$1 + \frac{2}{x_{2k+3}} < 1 + \frac{2}{x_{2k+1}}$$ $$x_{2k+3} > x_{2k + 1}$$ Not quite there yet, keep going... $$\vdots$$ $$x_{2k+2} < x_{2k}$$ Now we can prove the above statement using the inductive assumption.

---

Alternatively, if you want to be able to solve the entire problem...

Given that $x_{n+1} = 1 + \frac{2}{x_n}$, you can substitute $x = p/q$ to get:

$$\frac{p_{n+1}}{q_{n+1}} = 1 + \frac{2}{\frac{p_{n}}{q_{n}}} = \frac{p_{n} + 2~q_{n}}{p_{n}}$$

$$\begin{bmatrix} p_{n+1} \\ q_{n+1} \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} p_n \\ q_n \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}^n\begin{bmatrix} p_1 \\ q_1 \end{bmatrix}$$

Diagonalizing, you get:

$$\begin{bmatrix} p_{n+1} \\ q_{n+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ \frac 12 & -1 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & -1 \end{bmatrix}^n \begin{bmatrix} 1 & 1 \\ \frac 12 & -1 \end{bmatrix}^{-1} \begin{bmatrix} 1 \\ 1\end{bmatrix}$$ $$ = \begin{bmatrix} \frac{2^{n+2} - (-1)^n}{3} \\ \frac{2^{n+1} + (-1)^n}{3} \end{bmatrix}$$

So

$$x_n = \frac{2^{n+1} + (-1)^n}{2^{n} - (-1)^n}$$

Finishing,

$$x_{2k} = \frac{2^{{2k}+1} + (-1)^{2k}}{2^{2k} - (-1)^{2k}} = \frac{2^{2k+1} + 1}{2^{2k} - 1} = \frac{1}{1 - 2^{-2k}} - \frac{1}{-1 + 2^{2k}}$$

And as both denominators $1 - 2^{-2k}$ and $-1 + 2^{2k}$ are increasing, both terms are decreasing.