Question

Find the smallest integer $k$ for which the conditions

• $a_1, a_2, a_3, \ldots$ is a nondecreasing sequence of positive integers

• $a_n = a_{n-1} + a_{n-2}$ for all $n \gt 2$

• $a_9 = k$

are satisfied by more than one sequence.

Answer

Solution:

Iterating the recurrence gives $a_9 = 13a_1 + 21a_2,$ and the sequence is nondecreasing exactly when $0 \lt a_1 \le a_2$ (all later terms then take care of themselves). So we need the smallest $k$ for which $13x + 21y = k$ has two solutions with $0 \lt x \le y.$

Suppose $13x + 21y = 13u + 21v$ with $x \lt u.$ Then $13(u - x) = 21(y - v),$ so $u - x$ is a positive multiple of $21.$ Hence $u \ge x + 21 \ge 22,$ and since $u \le v,$ also $v \ge 22,$ giving $k = 13u + 21v \ge 34 \cdot 22 = 748.$

Conversely $k = 748$ works: $(x, y) = (1, 35)$ and $(22, 22)$ give the sequences $1, 35, 36, 71, 107, 178, 285, 463, 748$ and $22, 22, 44, 66, 110, 176, 286, 462, 748.$ The answer is $k = 748.$

2002 AIME I Problem 8

Solution:

Problem 8 in Other Years