Maths Olympiad Prep

Library / /212 of 462

Algebra Difficulty 5.7 AIME, harder Prove it Ireland

A sequence (un)n=0(u_n)_{n=0}^{\infty} is defined recursively as follows: u0=2u_0 = 2 and
un=2un1+1un1+2, for n=1,2,3, u_n = \frac{2u_{n-1} + 1}{u_{n-1} + 2}, \text{ for } n = 1, 2, 3, \dots
So, for example, u1=54u_1 = \frac{5}{4}, u2=1413u_2 = \frac{14}{13}. Prove that for all positive integers nn,
1<un<1+23n.1 < u_n < 1 + \frac{2}{3^n}.

Solutions — 2

Solution 1

Introduce a new sequence vn=un1v_n = u_n - 1. We have v0=1v_0 = 1 and the given recursion translates into
vn+1=2vn1+3vn1+3, i.e. vn=vn1vn1+3=13vn1+3. v_n + 1 = \frac{2v_{n-1} + 3}{v_{n-1} + 3}, \text{ i.e. } v_n = \frac{v_{n-1}}{v_{n-1} + 3} = 1 - \frac{3}{v_{n-1} + 3}.
We have to prove that 0<vn<23n0 < v_n < \frac{2}{3^n}. As v0=1>0v_0 = 1 > 0, the recursion easily implies that vn>0v_n > 0 for all n0n \ge 0.
Let us now show by induction that vn<23nv_n < \frac{2}{3^n}. The start at n=0n = 0 is clear, as v0=1<2v_0 = 1 < 2. Assume now that the inequality holds true for n=k0n = k \ge 0, i.e. vk<23kv_k < \frac{2}{3^k}. This assumption implies
vk+3<2+3k+13kand so3vk+3<3k+12+3k+1,hence v_k + 3 < \frac{2 + 3^{k+1}}{3^k} \quad \text{and so} \quad -\frac{3}{v_k + 3} < -\frac{3^{k+1}}{2 + 3^{k+1}}, \quad \text{hence}
vk+1=13vk+3<13k+12+3k+1=22+3k+1<23k+1. v_{k+1} = 1 - \frac{3}{v_k + 3} < 1 - \frac{3^{k+1}}{2 + 3^{k+1}} = \frac{2}{2 + 3^{k+1}} < \frac{2}{3^{k+1}}.

Solution 2

The sequence (un)n(u_n)_n^\infty begins 2,54,1413,4140,122121,365364,2, \frac{5}{4}, \frac{14}{13}, \frac{41}{40}, \frac{122}{121}, \frac{365}{364}, \dots, and helped by the occurrence of 3n3^n in the statement of the question, we check that the sequence (3n)n(3^n)_n^\infty begins 1,3,9,27,81,243,729,1, 3, 9, 27, 81, 243, 729, \dots, and we note the pattern (3n+1±1)/2\left(3^{n+1} \pm 1\right)/2 in the form of the numerators and denominators of the terms unu_n. We therefore conjecture
un=3n+1+13n+11, for all n0. u_n = \frac{3^{n+1} + 1}{3^{n+1} - 1}, \text{ for all } n \ge 0.
We prove the conjecture by simple induction. The formula is trivial for n=0n = 0. Assuming the validity of the conjecture for n=k0n = k \ge 0, we have
uk+1=2uk+1uk+2=2(3k+1+13k+11)+1(3k+1+13k+11)+2=2(3k+1+1)+(3k+11)(3k+1+1)+2(3k+11)=3k+2+13k+21, u_{k+1} = \frac{2u_k + 1}{u_k + 2} = \frac{2\left(\frac{3^{k+1}+1}{3^{k+1}-1}\right) + 1}{\left(\frac{3^{k+1}+1}{3^{k+1}-1}\right) + 2} = \frac{2(3^{k+1} + 1) + (3^{k+1} - 1)}{(3^{k+1} + 1) + 2(3^{k+1} - 1)} = \frac{3^{k+2} + 1}{3^{k+2} - 1},
as asserted. This proves the conjecture. It now follows immediately that un>1u_n > 1 and that
un1=23n+11<23n.u_n - 1 = \frac{2}{3^{n+1} - 1} < \frac{2}{3^n}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.