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

Answer: 748

Concepts:recursion Fibonacci Diophantine Equation

Difficulty rating: 2650

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

Answer: 748

Difficulty rating: 2650

Solution:

Problem 8 in Other Years