Maths Olympiad Prep

Library / /91 of 155

Number theory Difficulty 6.3 National olympiad Prove it Saudi Arabia

Let pp, qq be given primes and the sequence (pn)n1(p_{n})_{n \geq 1} defined recursively as follows: p1=pp_{1} = p; p2=qp_{2} = q and pn+2p_{n+2} is the largest prime divisor of the number (pn+pn+1+2016)(p_{n} + p_{n+1} + 2016) for all n1n \geq 1. Prove that this sequence is bounded, that is there exists a positive real number MM such that an<Ma_{n} < M for all positive integers nn.

Solution

Put k=2016k = 2016 and an=max{pn,pn+1}a_{n} = \max \{p_{n}, p_{n+1}\} for each n1n \geqslant 1.
We shall show that an+1an+k+2a_{n+1} \leqslant a_{n} + k + 2. In fact, since pn+1anp_{n+1} \leqslant a_{n}, it remains to show that pn+2an+k+2p_{n+2} \leqslant a_{n} + k + 2.
If pn+2=2p_{n+2} = 2 then the inequality is trivially true. It suffices to consider the case pn+2>2p_{n+2} > 2.
If either pn=2p_{n} = 2 or pn+1=2p_{n+1} = 2 then pn+2pn+pn+1+k=an+k+2p_{n+2} \leqslant p_{n} + p_{n+1} + k = a_{n} + k + 2. Otherwise, both primes pnp_{n} and pn+1p_{n+1} are odd, in particular pn+pn+1+kp_{n} + p_{n+1} + k is even. But pn+2>2p_{n+2} > 2, we get
pn+2pn+pn+1+k2<an+k+2. p_{n+2} \leqslant \frac{p_{n} + p_{n+1} + k}{2} < a_{n} + k + 2 .
It is clear that there is a positive integer ss such that a1s(k+3)!+1a_{1} \leqslant s(k+3)! + 1. We show, by induction that ans(k+3)!+1a_{n} \leqslant s(k+3)! + 1. Indeed, suppose this is true for nn, then
an+1an+k+2s(k+3)!+k+3. a_{n+1} \leqslant a_{n} + k + 2 \leqslant s(k+3)! + k + 3 .
If an+1>s(k+3)!+1a_{n+1} > s(k+3)! + 1, then 1<mk+31 < m \leqslant k + 3 with m=an+1q(k+3)!m = a_{n+1} - q(k+3)!. Hence, mm must be a divisor of (k+3)!(k+3)!, that is mm is a proper divisor of s(k+3)!+m=an+1s(k+3)! + m = a_{n+1}. However, this cannot happen since an+1a_{n+1} is a prime.
Thus, ans(k+3)!+1a_{n} \leqslant s(k+3)! + 1, and this completes the solution. \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 and solution reproduced as published; topic and difficulty added by this site.