Answer: 748

Small Hint:

Iterate the recurrence to express the target in the first two terms: $a_9 = 13a_1 + 21a_2$

Big Hint:

If $13x + 21y = 13u + 21v$ with $x \lt u,$ then $u - x$ is a multiple of $21,$ forcing $u$ and $v$ to be at least $22$

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.$