0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why are you subtracting $x_n - x_{n+1}$ $\endgroup$ – K Split X Jan 6 '17 at 3:13
  • $\begingroup$ To prove that $x_n-x_{n+1}>0$, which is the same with $x_{n+1}<x_n$ $\endgroup$ – Momo Jan 6 '17 at 3:40
  • $\begingroup$ @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. $\endgroup$ – PDE Jan 6 '17 at 4:02
  • $\begingroup$ @PDE Are you commenting on my proof or on yours? $\endgroup$ – Momo Jan 6 '17 at 5:21
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – benji Jan 6 '17 at 3:46
  • $\begingroup$ @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). $\endgroup$ – Momo Jan 6 '17 at 3:48
  • $\begingroup$ 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. $\endgroup$ – JimmyK4542 Jan 6 '17 at 3:54
  • $\begingroup$ If you allow $x_n<2-\sqrt 3$, then you can no longer guarantee $x_{n+1}<x_n$ $\endgroup$ – Momo Jan 6 '17 at 3:57
  • $\begingroup$ ^Ahh yes, my bad. Let me fix that. $\endgroup$ – JimmyK4542 Jan 6 '17 at 3:58
0
$\begingroup$

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$

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

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!

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – Momo Jan 6 '17 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.