Proof by induction of a recursive sequence

Question

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002:

---

Q

The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and $$u_{n+1}=\frac{5u_n+4}{u_n+2}$$By considering $4-u_{n+1}$, or otherwise, prove by induction that $u_n<4$ for all $n\geq1$.

Prove also that $u_{n+1}>u_n$ for all $n\geq 1$.

---

Here is my solution

To Prove the Initial Relation $u_n<4$

By using long division: $$\frac{5u_n+4}{u_n+2}\equiv 5-\frac{6}{u_n+2}$$ For $n=1$ $$u_{2}= 5-\frac{6}{u_1+2}$$ Since $u_1<4$ then, $$\frac{6}{u_1+2}>1$$ and, $$5-\frac{6}{u_1+2}<4$$ therefore, $$u_{2}<4$$

thus the statement is true for $n=1$

Conjecture: The statement is true for $n=k$

$$u_{k}<4$$

Since $u_{k+1}<4$ ... (proved above for $n=1$), then, $$\frac{6}{u_{k+1}+2}>1$$ and, $$5-\frac{6}{u_{k+1}+2}<4$$ therefore, $$u_{k+2}<4$$

Since the statement is true for $n=k$, $n=k+1$, and $n=1$, the given relation ($u_n<4$) is correct.

---

To prove that $u_{n+1}>u_n$:

$$u_{n+1}-u_n=\frac{5u_n+4}{u_n+2}-u_n\equiv -\frac{(u_n)^2+3u_n+4}{u_2+2}$$ $$-\frac{(u_n)^2+3u_n+4}{u_2+2}\equiv \frac{(4-u_n)(u_n+1)}{u_n+2}>0$$ Since, $$u_{n+1}-u_n>0$$ $$u_{n+1}>u_n$$

---

---

I am not sure if my solution to the first part is correct, and even if it is correct, I didn't use the relation $4-u_{n+1}$ so it would be really great if someone suggests abetter solution using the relation mentioned in the question.

As for second part, I am pretty confident that it is correct, but I am open to suggestions.

Answer 1

What they mean is that you should observe that $$4-u_{n+1}=4-\frac{5u_n+4}{u_n+2}=\frac{4-u_n}{u_n+2}$$ From this it is clear that if $4-u_n>0$, then $4-u_{n+1}>0$ and the gap gets smaller, so $u_n$ is increasing (to $4$ very fast).

Answer 2

For the record, this is a Ricatti recurrence, as $5 \cdot 2 - 1 \cdot 4 \ne 0$. There are at least three solution ideas around, I like Mitchell's "An Analytic Riccati solution for Two-Target Discrete-Time Control", Journal of Economic Dynamics and Control 24(4), pp 615-622 (2000).

Take: $$ u_{n + 1} = \frac{a u_n + b}{c u_n + d} $$ Define a new variable by: $$ x_n = \frac{1}{1 + \eta u_n} $$ Substituting into the recurrence gives: $$ x_{n + 1} = \frac{(d \eta - c) x_n + c} {(b \eta^2 - (a - d) \eta - c) x_n + a \eta + c} $$ Selecting $\eta$ such that $b \eta^2 - (a - d) \eta - c = 0$ you get a linear first-order recurrence. Here: $$ 4 \eta^2 -3 \eta - 1 = 0 $$ gets $\eta = 1$ or $\eta = -1/4$. First is simpler, pick that one: $$ x_{n + 1} = \frac{(2 \cdot 1 - 1) x_n + 2}{5 \cdot 1 + 1} = \frac{x_n + 1}{6} $$ We just have a limit on $u_1$, but we can just shift by one without changing anything. We get: $$ x_1 = \frac{1}{1 + u_1} $$ Use generating functions to solve the linear recurrence by defining $X(z) = \sum_{n \ge 0} x_{n + 1} z^n$, multiplying by $z^n$ and summing over $n \ge 0$: $$ \frac{X(z) - x_1}{z} = \frac{X(z)}{6} + \frac{1}{6} \cdot \frac{1}{1 - z} $$ to get: $$ X(z) = \frac{1}{5 (1 - z)} + \frac{5 x_1 - 1}{5} \cdot \frac{1}{1 - z/6} $$ The coefficients are immediate: $$ x_{n + 1} = \frac{1}{5} + \frac{5 x_1 - 1}{5} \cdot 6^{-n} $$ Going back to the original variables: \begin{align} u_n &= \frac{4 (u_1 + 1) \cdot 6^n + (u_1 - 4)} {(u_1 + 1) \cdot 6^n - (u_1 - 4)} &= 4 - \frac{5 (4 - u_1)}{(u_1 + 1) \cdot 6^n + (4 - u_1)} \end{align} If $u_1 < 4$, the second term is always positive, and $u_n < 4$. In that case, the second term decreases as $n$ increases, so $u_{n + 1} > u_n$.

Answer 3

Simpler: By the hypotheses, $0 < u_1 < 4$. If you define an auxiliary sequence: $$ v_n = 4 - u_n $$ I.e., $u_n = 4 - v_n$, you have: $$ v_{n + 1} = \frac{v_n}{6 - v_n} $$ If $0 < v_n < 4$, $v_{n + 1} > 0$. We need the maximal value of $\frac{v}{6 - v}$ in the range $0 < v < 4$. We see that as $v$ increases the numerator increases and the denominator decreases, so up to $v < 6$ the function is increasing. The maximum in our range is at $v = 4$, so that $v_{n + 1} < 2$, and we are clear.

For the second part, as by the above $0 < v_n < 4$: $$ u_{n + 1} - u_n = v_n - v_{n + 1} = v_n \left(1 - \frac{1}{6 - v_n} \right) > 0 $$