Maths Olympiad Prep

Library / /23 of 24

Algebra Difficulty 7.8 National olympiad, round 2 Prove it Netherlands

For a given value tt, we consider number sequences a1,a2,a3,a_1, a_2, a_3, \dots such that an+1=an+tan+1a_{n+1} = \frac{a_n + t}{a_n + 1} for all n1n \ge 1.

a. Suppose that t=2t = 2. Determine all starting values a1>0a_1 > 0 such that 43an32\frac{4}{3} \le a_n \le \frac{3}{2} holds for all n2n \ge 2.

b. Suppose that t=3t = -3. Investigate whether a2020=a1a_{2020} = a_1 for all starting values a1a_1 different from 1-1 and 11.

Solution

a. First, we determine for what starting values a1>0a_1 > 0 the inequalities 43a232\frac{4}{3} \le a_2 \le \frac{3}{2} hold. Then, we will prove that for those starting values, the inequalities 43an32\frac{4}{3} \le a_n \le \frac{3}{2} are also valid for all n2n \ge 2.

First, we observe that a2=a1+2a1+1a_2 = \frac{a_1+2}{a_1+1} and that the denominator, a1+1a_1 + 1, is positive (since a1>0a_1 > 0). The inequality
43a2=a1+2a1+132, \frac{4}{3} \le a_2 = \frac{a_1 + 2}{a_1 + 1} \le \frac{3}{2},
is therefore equivalent to the inequality
43(a1+1)a1+232(a1+1), \frac{4}{3}(a_1 + 1) \le a_1 + 2 \le \frac{3}{2}(a_1 + 1),
as we can multiply all parts in the inequality by the positive number a1+1a_1 + 1. Subtracting a1+2a_1 + 2 from all parts of the inequality, we see that this is equivalent to
13a123012a112. \frac{1}{3}a_1 - \frac{2}{3} \le 0 \le \frac{1}{2}a_1 - \frac{1}{2}.
We therefore need to have 13a123\frac{1}{3}a_1 \le \frac{2}{3} (i.e. a12a_1 \le 2), and 1212a1\frac{1}{2} \le \frac{1}{2}a_1 (i.e. 1a121 \le a_1 \le 2). The starting value a1a_1 must therefore satisfy 1a121 \le a_1 \le 2.

Now suppose that 1a121 \le a_1 \le 2, so that a2a_2 satisfies 43a232\frac{4}{3} \le a_2 \le \frac{3}{2}. Looking at a3a_3, we see that a3=a2+2a2+1a_3 = \frac{a_2+2}{a_2+1}. That is the same expression as for a2a_2, only with a1a_1 replaced by a2a_2. Since a2a_2 also satisfies 1a221 \le a_2 \le 2, the same argument now shows that 43a332\frac{4}{3} \le a_3 \le \frac{3}{2}.

We can repeat the same argument to show this for a4a_4, a5a_5, etcetera. Hence, we find that 43an32\frac{4}{3} \le a_n \le \frac{3}{2} holds for all n2n \ge 2. The formal proof is done using induction: the induction basis n=2n = 2 has been shown above. For the induction step, see the solution of part (b) of the version for klas 5 & klas 4 and below. The result is that all inequalities hold if and only if 1a121 \le a_1 \le 2.

b. Let's start by computing the first few numbers of the sequence in terms of a1a_1. We see that
a2=a13a1+1 a_2 = \frac{a_1 - 3}{a_1 + 1}
and
a3=a23a2+1=a13a1+13a13a1+1+1=a133(a1+1)a13+(a1+1)=2a162a12=a13a11. \begin{aligned} a_3 &= \frac{a_2 - 3}{a_2 + 1} = \frac{\frac{a_1-3}{a_1+1} - 3}{\frac{a_1-3}{a_1+1} + 1} = \frac{a_1 - 3 - 3(a_1 + 1)}{a_1 - 3 + (a_1 + 1)} \\ &= \frac{-2a_1 - 6}{2a_1 - 2} = \frac{-a_1 - 3}{a_1 - 1}. \end{aligned}
Here, it is important that we do not divide by zero, that is, a11a_1 \ne -1 and a21a_2 \ne -1. The first inequality follows directly from the assumption. For the second inequality we consider when a2=1a_2 = -1 holds. This is the case if and only if a13=(a1+1)a_1 - 3 = -(a_1 + 1), if and only if a1=1a_1 = 1. Since we assumed that a11a_1 \ne 1, we see that a21a_2 \ne -1. The next number in the sequence is
a4=a33a3+1=a13a113a13a11+1=a133(a11)a13+(a11)=4a14=a1. a_4 = \frac{a_3 - 3}{a_3 + 1} = \frac{\frac{-a_1-3}{a_1-1} - 3}{\frac{-a_1-3}{a_1-1} + 1} = \frac{-a_1 - 3 - 3(a_1 - 1)}{-a_1 - 3 + (a_1 - 1)} = \frac{-4a_1}{-4} = a_1.
Again, we are not dividing by zero since a3=1a_3 = -1 only holds when a13=a1+1-a_1 - 3 = -a_1 + 1, which is never the case.

We see that a4=a1a_4 = a_1. Since an+1a_{n+1} only depends on ana_n, we see that a5=a2a_5 = a_2, a6=a3a_6 = a_3, a7=a4a_7 = a_4, etcetera. In other words: the sequence is periodic with period 3, and we see that
a2020=a2017=a2014==a4=a1. a_{2020} = a_{2017} = a_{2014} = \dots = a_4 = a_1.
To conclude: indeed we have a2020=a1a_{2020} = a_1 for all starting values a1a_1 unequal to 1 and 1-1.

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 and solution reproduced as published; topic and difficulty added by this site.