Maths Olympiad Prep

Library / /19 of 36

Algebra Difficulty 5.9 AIME, harder Prove it Saudi Arabia

Find all pairs (b,c)(b, c) of positive integers, such that the sequence defined by a1=ba_1 = b, a2=ca_2 = c and
an+2=4an+13an,n1 a_{n+2} = |4a_{n+1} - 3a_n|, \forall n \ge 1
has only finite number of composite terms.

Solution

Suppose firstly that there exists a k2k \ge 2 such that ak+1>aka_{k+1} > a_k. Then by induction we have an+1>ana_{n+1} > a_n for all nkn \ge k (when taking out the modulus the expression does not change sign) and so an+2=4an+13ana_{n+2} = 4a_{n+1} - 3a_n for all nkn \ge k. Solving the characteristic equation t24t+3=0t^2 - 4t + 3 = 0 implies that
an=C1+C23n,nk. a_n = C_1 + C_2 \cdot 3^n, \forall n \ge k.
Since the sequence is strictly increasing, we must have C2>0C_2 > 0 and in particular any prime divisor pp of some am2a_m \ge 2 will also be a prime divisor of am+k(p1)a_{m+k(p-1)} for any k0k \ge 0 as 3m+k(p1)3m(modp)3^{m+k(p-1)} \equiv 3^m \pmod{p} by Fermat's Little theorem. In particular, infinitely many terms would be composite.

Therefore ak+1aka_{k+1} \le a_k for all k2k \ge 2. Since ak>0a_k > 0, we must have an=pa_n = p where pp is a prime for all nn0n \ge n_0 with some positive integer n0n_0. Thus
p=4p3an1    an1{p,3p}. p = |4p - 3a_{n-1}| \implies a_{n-1} \in \{p, 3p\}.
The former case gives us (b,c)=(p,p)(b, c) = (p, p) which indeed satisfies the condition. Let's consider the latter case: an1=3pa_{n-1} = 3p, so we can find out that an2=4p±p3a_{n-2} = 4p \pm \frac{p}{3}. We consider some cases:

* If there is no an2a_{n-2}, then (b,c)=(3p,p)(b, c) = (3p, p) are the first two terms.
* If pp is divisible by 33, thus p=3p = 3, an1=9a_{n-1} = 9, an2=11a_{n-2} = 11 or 1313, which implies an3a_{n-3} being not integer.

So, finally we get (b,c){(11,9),(13,9),(p,p),(3p,p)}(b, c) \in \{(11, 9), (13, 9), (p, p), (3p, p)\} where pp is any prime. \square

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.