The Smallest Possible 2014th Term

We start with the following lemma.

---

Lemma: $a_{n+1} > a_n + a_{n-1} \quad \forall \ n \in \mathbb{N}$

Proof: Note that $\gcd (a_{n+1}, a_n) = \gcd (a_{n+1} - a_n, a_n),$ and $\gcd (a_{n+1}-a_n, a_n) \leq a_{n+1}-a_n.$ Since $\gcd (a_{n+1}, a_n) > a_{n-1},$ we have that $a_{n+1} - a_n > a_{n-1} \implies a_{n+1} > a_n + a_{n-1},$ which is what we wanted. $\blacksquare$

---

Now we shall prove by strong induction that $a_n \geq 2^{n-1}$ for all $n \in \mathbb{N}.$

Base case: $n= 1, 2, 3, 4$

• $n=1:$ We trivially have $a_1 \geq 1= 2^0,$ since all $a_i$ 's are defined to be positive.

• $n=2:$ Note that if $a_2=1,$ we would have $\gcd (a_3, a_2) = 1 = a_1,$ which is not allowed. Thus, $a_2 \geq 2 = 2^1.$

• $n=3:$ By the lemma, $a_3 > a_2 + a_1 \geq 2+1= 3,$ so $a_3 \geq 4 = 2^2.$

• $n=4:$ Again, by the lemma, $a_4 > a_3 + a_2 \geq 4+2 = 6,$ so $a_4 \geq 7.$ However, if $a_4=7,$ we would have $\gcd (a_4, a_3) = 1 = a_1,$ since $a_4 > a_3$ and $7$ is a prime.

Our base cases are complete.

Inductive step

Assume our assertion is true for $1, 2, \cdots , k-1, k$ for some $k \in \mathbb{N,}$ so $a_n \geq 2^{n-1}$ for all $n \leq k.$ On the contrary, assume $a_{k+1} < 2^k.$ Note that, by the lemma, $a_{k+1} > a_k + a_{k-1} > 2^{k-1} + 2^{k-2} = \dfrac{3}{2} \cdot 2^{k-1}.$ Let $a_{k+1} = j \cdot \gcd (a_{k+1}, a_k).$ Since $\gcd (a_{k+1}, a_k) > 2^{k-2},$ $j \leq \dfrac{a_{k+1}}{2^{k-2}} < \dfrac{2^k}{2^{k-2}} = 4.$

• Case 1: $j=1$

This implies $a_{k+1} = \gcd (a_{k+1}, a_k) \implies a_{k+1} \mid a_k \implies a_{k+1} \leq a_k,$ contradiction.

• Case 2: $j=2$

This implies $a_{k+1} = 2 \gcd (a_{k+1}, a_k),$ so $\dfrac{a_{k+1}}{2}$ divides $a_k.$ Note that $\dfrac{a_k}{2} < \dfrac{a_{k+1}}{2} < a_k,$ which shows that this isn't possible (no integer $x$ can have a divisor in the range $\left( \dfrac{x}{2}, x \right)$ ).

• Case 3: $j=3$

This implies $a_{k+1} = 3 \gcd (a_{k+1}, a_k).$ Note that $a_k < a_{k+1},$ so $a_k$ is either equal to $\gcd (a_{k+1}, a_k)$ or $2 \gcd (a_{k+1}, a_k).$ However, if $a_k = \gcd (a_{k+1}, a_k),$ $a_{k+1} = 3a_k > 3 \cdot 2^{k-1} > 2^k,$ contradiction. Hence $a_k= 2 \gcd (a_{k+1}, a_k)$ and $a_{k+1} = \dfrac{3}{2}a_k.$

Let $a_k = m \gcd (a_k, a_{k-1}).$ We can similarly reject the cases $m= 1, 2.$

• Subcase 1: $m \geq 6$

Then, $a_k = \dfrac{2}{3} a_{k+1} > 6 \cdot 2^{k-3} \implies a_{k+1} > 9 \cdot 2^{k-3} > 8 \cdot 2^{k-1} = 2^k,$ contradiction.

• Subcase 2: $3 \leq m \leq 4$

Then, $a_{k-1} < \dfrac{4}{2} \gcd (a_k, a_{k-1}) = 2 \gcd (a_k, a_{k-1}),$ which implies $a_{k-1} = \gcd (a_{k-1}, a_k),$ or $a_{k-1} \mid a_k.$ Since $a_{k-1} < a_k,$ $a_k \geq 3 a_{k-1}$ and $a_{k+1} = \dfrac{3}{2} a_k \geq \dfrac{3}{2} \cdot 3 a_{k-1} > \dfrac{9}{2} a_{k-1} > 4 a_{k-1} > 4 \cdot 2^{k-2} = 2^k,$ contradiction.

• Subcase 3: $m=5$

This gives $a_{k+1}= \dfrac{15}{2} \gcd (a_k, a_{k-1}),$ and $a_{k-1} \leq \dfrac{a_{k+1}}{3} = \dfrac{5}{2} \gcd (a_k, a_{k-1}),$ so $a_{k-1}$ is either $\gcd (a_k, a_{k-1})$ or $2 \gcd (a_k, a_{k-1}).$ Let $a_{k-1} = i \cdot \gcd (a_{k-2}, a_{k-3}).$ Note that $a_{k-1}$ divides $2 \gcd (a_k, a_{k-1}),$ so $2 \gcd (a_k, a_{k-1}) = g \cdot \gcd (a_{k-2}, a_{k-3})$ for some $g \in \mathbb{N}.$ Once again, we do casework on $g.$ We can similarly reject the cases $g= 1,2.$

• Sub-sub case 1: $g \geq 5$

Then, $a_{k+1} \geq \dfrac{75}{4} \gcd (a_{k-1}, a_{k-2}) > \dfrac{75}{4} \cdot 2^{k-4} = 75 \cdot 2^{k-6} > 64 \cdot 2^{k-6} = 2^k,$ contradiction.

• Sub-sub case 2: $3 \leq g \leq 4$

Then, similar to subcase 2, $a_{k-2} = \gcd (a_{k-1}, a_{k-2}),$ and $a_{k+1} \geq 3 \times \dfrac{15}{4} a_{k-2} > 45 \cdot 2^{k-4} > 16 \cdot 2^{k-4} = 2^k,$ contradiction.

Now that we have covered all cases, our inductive step is complete. $\blacksquare$

---

We then have $a_n \geq 2^{n-1}$ for all $n \in \mathbb{N}.$ The sequence $\{2^{i-1}\}_{i=1}^{\infty}$ obviously satisfies the given condition, since $\gcd (2^i, 2^{i+1}) = 2^i > 2^{i-1} \quad \forall \ i \in \mathbb{N}.$ Thus, the minimum possible value of $a_{2014}$ is $2^{2013},$ so $N= 2^{2013} \implies 2N = 2^{2014}.$ Evaluating this modulo $1000,$ we find out that the last three digits of $2N$ are $\boxed{384}.$

---

This problem is taken from ISL 2008 N3 .

FANTASTIC PROBLEM! I found this sequence to satisfy the given conditions: $1, 2, 4, 8, \dots 2^{n-1}$ where $a_n=2^{n-1}$ . This is obviously the smallest possible sequence, another example would be $1, 3, 9, 27, 81, \dots$ . Since the sequence has to have the least possible common ratio, and the least integral first term, the first sequence ( $1, 2, 4, 8, \dots$ ) is indeed the smallest. Thus we want to calculate $2 \times 2^{2014-1} \Longrightarrow 2 \times 2^{2013} \Longrightarrow 2^{2014}$ . Now, evaluating $2^{2014} \pmod{1000}$ , we get $\boxed{384}$ .