Let $ p $ and $ q $ be given primes and the sequence $ \{ p_n \}_{n = 1}^{\infty} $ defined recursively as follows: $ p_1 = p $, $ p_2 = q $, and $ p_{n+2} $ is the largest prime divisor of the number $( p_n + p_{n + 1} + 2016) $ for all $ n \geq 1 $. Prove that this sequence is bounded. That is, there exists a positive real number $ M $ such that $ p_n < M $ for all positive integers $ n $.
Problem
Source:
Tags: sa, Sequences
integralE
08.08.2018 13:03
Solution: For the sake of contradiction assume the contrary, \begin{align*} \big( \forall M \in \mathbb{N} \big) \big( \exists n : p_{n + 1} > M \big). \end{align*}By the well-ordering principle, let $ n + 1 $ be the minimal natural number such that $ p_{n + 1} $ is larger than some fixed $M$, large enough suitable for our purposes (as we will see $ M = m! + 1 > 2016^{2016} $ ). Because of the definition of $ p_{n + 1} $ we find that \begin{align*} p_{n - 1}, p_n \leq M < p_{n + 1}. \end{align*}On the other hand, \begin{align*} p_{n + 1} \leq p_{n} + p_{n - 1} + 2016, \end{align*}by the problem's condition. If \begin{align*} p_{n + 1} & \leq \frac{ p_{n} + p_{n - 1} + 2016}{3} \\ & \leq \frac{2}{3}\big( M + 1008 \big), \\ \end{align*}we get \begin{align*} M < p_{n + 1} \leq \frac{2}{3}\big( M + 1008 \big), \\ \end{align*}hence, a contradiction for $M > 2016^{2016}$. Hence, \begin{align*} p_{n + 1} \in \{ \frac{p_{n} + p_{n- 1} + 2016}{2}, p_{n} + p_{n - 1} + 2016 \}. \end{align*}Take $ M = m! + 1 $, where $ m > 2019 $. If $ \quad p_{n + 1} = \frac{p_{n} + p_{n- 1} + 2016}{2}, $ we get \begin{align*} M + 1 \leq p_{n + 1} & \leq \frac{2M + 2016}{2} \\ & = M + 1008 \\ \end{align*}But, note that all of $M + 1, \ M + 2, \ldots, \ M + 1008 $ are composite numbers since \begin{align*} M + t & = m! + t+ 1\\ & = (t + 1)(\frac{m!}{t + 1} + 1) \end{align*}for $ t + 1 < 1010 < m $. The only option left is \begin{align*} p_{n + 1} = p_n + p_{n - 1} + 2016. \end{align*}However, if both $ p_n, p_{n - 1} $ are odd primes, then $p_{n + 1} $ would be even, a contradiction. Hence, $p_x = 2 $ for one $x \in \{ n - 1, n \} $. Let $ y $ be the other index ( $ y = \{ n - 1, n \} - \{ x \} $ ). We have \begin{align*} p_{n + 1} & = p_y + 2018 \\ & \leq M + 2018 \\ \end{align*}Hence, \begin{align*} M + 1 \leq p_{n + 1} \leq M + 2018. \end{align*}Similarly as before, we find that $ p_{n + 1} $ is not prime. Thus we have a contradiction and our basic assumption was wrong. This implies that the sequence $ \{ p_n \}_{n = 1}^{\infty} $ is bounded from above. $\blacksquare$ Tags: Solution, prime number definition, inequality, factorials. Remark: The same solution holds if we replace $ 2016 $ by $ 2c $ for any natural number $ c $.