2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The proof is basically right. You need not have proved the case $n=2$. The suggested substitution is not all that helpful, but it does make things more mechanical. $\endgroup$ – André Nicolas Apr 16 '14 at 20:21
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Really appreciate that you went into detail, but I think the depth of your answer is more than requirement of my syllabus (but would definitely help other seeking in-depth knowledge) and what I can comprehend. I'll mark this question answered by user2345215 $\endgroup$ – Uzair Apr 17 '14 at 20:12
  • $\begingroup$ @Uzair, don't worry. I was doing this just to see how it turned out. got an example out of it tooo $\endgroup$ – vonbrand Apr 17 '14 at 22:21
0
$\begingroup$

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 $$

$\endgroup$

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.