Nemotron-IMO-Bench 2026 C5

Let $0<a_1<a_2<\ldots$ be an increasing sequence of positive integers such that for any $n>1$ and any $\varepsilon_1,\ldots, \varepsilon_{n-1}\in \{0,1\}$ $$a_n\ne \varepsilon_1a_1+\ldots+\varepsilon_{n-1} a_{n-1}.$$ Let $N_M$ be the number of terms of the sequence $(a_n)_{n\geq 1}$ not exceeding $M$. Prove that for all $M>k$ $$N_M\leq a_k+\frac{M}{k+1}.$$