# Let $x_1 = 3, x_{n+1} = \frac{1}{4-x_n}, \text{for } n \geq 1$. Use induction to show that $0 < x_{n+1} < x_n < 4, \forall n \in \mathbb{N}$.

Let

$$x_1 = 3, x_{n+1} = \frac{1}{4-x_n}, \text{for } n \geq 1$$

Use induction to show that $0 < x_{n+1} < x_n < 4, \forall n \in \mathbb{N}$.

Let $S(n)$ be the proposition that $0 < x_{n+1} < x_n < 4$.

Base Case:

$S(1)$, and thus $x_1 = 3$, $x_2 = \frac{1}{4-3} = 1$. We have $0 < 1 < 3 < 4$, thus $S(1)$ holds.

Inductive Hypothesis (strong):

Assume that $S(n)$ holds for $1 \leq i \leq n$.

Assume $S(i)$ holds therefore. So, $0 < x_{i+1} < x_i < 4$

Inductive Step:

Show that $S(i + 1)$ holds.

This is where I am stuck on the IS. Any suggestions?

What you really need to prove by induction is the stronger statement that $x_n$ is decreasing and: $$S(n):2-\sqrt 3<x_{n+1}<x_n\le3$$

$S(1)$ is obviously true. Then if $S(n-1)$ is true ($2-\sqrt 3<x_n<x_{n-1}\le3$) then:

$$x_{n+1}=\frac{1}{4-x_n}>\frac{1}{4-(2-\sqrt 3)}=2-\sqrt 3$$

$$x_n-x_{n+1}=x_n-\frac{1}{4-x_n}=\frac{-x_n^2+4x_n-1}{4-x_n}=\frac{3-(x_n-2)^2}{4-x_n}>0$$

since ${4-x_n}>0$ (obviously), and $3-(x_n-2)^2>0$ is equivalent to $2-\sqrt 3<x_n<2+\sqrt 3$, which is also true by the hypothesis of induction.

So you proved that $2-\sqrt 3<x_{n+1}<x_n\le3$ , which is exactly $S(n)$. Done.

• Why are you subtracting $x_n - x_{n+1}$ – K Split X Jan 6 '17 at 3:13
• To prove that $x_n-x_{n+1}>0$, which is the same with $x_{n+1}<x_n$ – Momo Jan 6 '17 at 3:40
• @Momo $2−sqrt{3} < x_{n+1} < x_n ≤ 3$ does not by itself imply $S_n$. The upper bound is OK, but the lower bound does not. But of course, fixing the lower-bound issue is easy. – PDE Jan 6 '17 at 4:02
• @PDE Are you commenting on my proof or on yours? – Momo Jan 6 '17 at 5:21

If $x_n < 4$, then $x_{n+1} = \dfrac{1}{4-x_n} < x_n$ holds iff $1 < x_n(4-x_n)$, i.e. $x_n^2-4x_n+1 < 0$.

This is equivalant to $(x_n-2)^2 < 3$, which holds for $2-\sqrt{3} < x_n < 2+\sqrt{3} \approx 3.73$.

So $0 < x_n < 4$ isn't a strong enough assumption to prove the inductive hypothesis.

Instead, try to show that $2-\sqrt{3} < x_{n+1} < x_n < 2+\sqrt{3}$ for all $n$ (which is a stronger statement).

• I think the problem is actually with the lower bound, because $x_1 = 3 \lt 2+\sqrt 3$. The statement should be stronger in the other direction as well $2-\sqrt 3 \lt x_{n+1} \lt x_n \lt 2 + \sqrt 3$ – benji Jan 6 '17 at 3:46
• @benji Yes, it is the lower bound which is the most important, the upper is not that much important (I did exactly that in my solution). – Momo Jan 6 '17 at 3:48
• Yes, it is just as easy to show that "$2-\sqrt{3} < x_{n+1} < x_n < 2+\sqrt{3}$ for all $n$" using induction. However, proving "$0 < x_{n+1} < x_n < 2+\sqrt{3}$ for all $n$" is sufficient for the given question. – JimmyK4542 Jan 6 '17 at 3:54
• If you allow $x_n<2-\sqrt 3$, then you can no longer guarantee $x_{n+1}<x_n$ – Momo Jan 6 '17 at 3:57
• ^Ahh yes, my bad. Let me fix that. – JimmyK4542 Jan 6 '17 at 3:58

Having proven the base case $S_1$, assume that, indeed,

$$x_{i+1} = \frac{1}{4-x_i}.$$

By induction,

$$x_{i+2} = \frac{1}{4-x_{i+1}} = \frac{1}{4-\frac{1}{4-x_i}}=\frac{4-x_i}{15-4x_i}.$$

Find the values of $x_i$ for which $S_{i+1}$ is true. Yet for $S_{i+1}$ to be true, it is necessary (but insufficient) to show that $x_{i+2} < x_{i+1}$ is likewise true. Therefore, the problem reduces to showing that for all natural numbers $i > 1$,

$$\frac{4-x_i}{15-4x_i} < \frac{1}{4-x_i}$$

That is, \begin{align} 15 - 4x_i & > 16 - 8x_i + x_{i}^2 \\ 0 & > x_{i}^2-4x_n+1 \\ & > (x_{i}^2-4x_n+4)-3 \\ 0 & > (x_i-2)^2 - 3 \\ 3 & > (x_i-2)^2 \\ -\sqrt{3} &< x_i-2 < \sqrt{3} \\ 0 &< 2-\sqrt{3} < x_i < 2+\sqrt{3} \\. \end{align}

This last result is exactly $S_i$. More specifically, the last block of equations proves that $S_i$ iff $S_{i+1}$. Q.E.D. $\blacksquare$

• There is a $4-x_i$ which got lost in translation when you calculated $x_{i+2}$ – Momo Jan 6 '17 at 3:44
• @Momo Where? Thanks for letting me know! – PDE Jan 6 '17 at 3:56
• $x_{i+2}\ne\frac{1}{15-4x_i}$ :( – Momo Jan 6 '17 at 3:59
• @Momo I've fixed it. – PDE Jan 6 '17 at 4:28
• ...but $2-\sqrt 3<x_i$ does not follow from the hypothesis of induction, so at the very least needs to be proved separately. – Momo Jan 6 '17 at 5:22

I thought I would post an answer without changing the induction (though there's nothing wrong with doing that!)
We assume: $$0 \lt x_{i+1} \lt x_i \ldots \lt x_1=3 < 4$$ We need to show: $$0 \lt x_{i+2} \lt x_{i+1} \lt 4$$ First, $x_{i+1} \lt \ldots x_1 \lt 4$
If we can show that $x_{i+2} \lt x_{i+1}$ then $x_{i+2} \lt 4$ and then $x_{i+2} = 1/(4-x_{i+1}) \gt 0$

So let's show that $x_{i+2} \lt x_{i+1}$

$$x_{i+2} = \frac{1}{4-x_{i+1}} \lt x_{i+1} \iff 2 - \sqrt 3 \lt x_{i+1} \lt 2+\sqrt 3$$

We know that $x_{i+1} < x_1 = 3 < 2+\sqrt 3$

Let's assume that $x_{i+1} \le 2-\sqrt 3$ then $$x_{i+1} = \frac{1}{4-x_i} \le 2- \sqrt 3$$ Simplifying this gives $x_i \le 2 - \sqrt 3$ but then $x_{i-1} \le 2 - \sqrt 3$ this leads to $x_1 \le 2 - \sqrt 3$ which is a contradiction!

• In other words you've proved $2-\sqrt 3<x_i<2+\sqrt 3$ in a separate induction, just to avoid adding it to the original induction :) – Momo Jan 6 '17 at 5:28