Let {$a_n$}$_{1}^{\infty}$ be array such that $a_1=2$ and for every $n\ge1$ $a_{n+1}=2^{a_n}+2$. Let $m,n$ be positive integers such that $m<n$. Prove that $a_m|a_n$.
Problem
Source: Serbia EGMO TST 2015
Tags: number theory
MathStudent2002
15.11.2015 19:58
Also 2015 ELMO #1
trumpeter
15.11.2015 20:00
It suffices to prove that $a_m\left|a_{m+1}\right.$.
But this is just 2015 ELMO #1.
Oops MathStudent2002 beat me to that
AleksaS
25.08.2020 17:14
Well known claim: If $a$ and $b$ are natural numbers, it is well known that $2^a + 1 | 2^b + 1$ if and only if $a | b$ and $\frac{b}{a}$ is odd number. We finish solution by induction. Let's suppose that for every $n > 3$, $a_i | a_j$ holds for any $i < j < n$. Now because $a_{n-3}$ and $a_{n-2}$ are divisible by $2$ but not by $4$ it means that $\frac{a_{n-2}}{a_{n-3}}$ is odd. From this we have $2^{a_{n-3}} + 1 = a_{n-2} -1$ which divides $2^{a_{n-2} - 1} + 1 = a_{n - 1} - 1$. From this $2^{a_{n-2} - 1} + 1 = \frac{a_{n -1}}{2}$ which divides $2^{a_{n-1} - 1} + 1 = \frac{a_n}{2}$ thus $a_{n -1} | a_n$ and from there $a_m | a_n$ for every $m < n$ which follows from induction.