Determine all sequences $a_1, a_2, a_3, . . . $ of nonnegative integers such that $a_1 \lt a_2 \lt a_3 \lt · · ·$

Question

Determine all sequences $a_1, a_2, a_3, . . . $ of nonnegative integers such that $a_1 \lt a_2 \lt a_3 \lt · · ·$ and $a_n$ divides $a_{n-1}+n$ for all $n\ge2$.

I know that one obvious possible sequence is $a_n=a_{n-1}+n$ but I don't know how to prove this is the only one or if there is more

from the 2018 SAMO senior round 3 http://www.samf.ac.za/content/files/QuestionPapers/s3q2018.pdf

Answer 1

I will try and prove that $a_n = a_{n-1} + n$ isn't the only solution.

$a_n$ divides $a_{n-1}+n$, So we can take 'm' to be the quotient. Note that m is an integer.

This gives us $ma_n=a_{n-1}+n$

Putting n=2 we get, $ma_2 = a_1 + 2$

As $a_2>a_1$ and both of them being being integers, $a_2-a_1\ge1$

$a_2\ge a_1+1$

$a_2 +1\ge a_1+2$

$a_2 +1\ge ma_2$

$(m-1)a_2\le 1$

$m\le {a_2+1\over a_2}$, Note that $a_2\ge 1$.

Trying out any value of $a_2$, we get, $m\le 2$ and because $m$ is an integer, $m=1$ or $m=2$.

Which give us $a_n=a_{n-1}+n$ or $2{a_n}=a_{n-1}+n$

Solve the first equation by telescopy and I don't know how to solve the second equation.

For first equation you will get $a_n= a_1 -1 + {n^{2}+n \over 2}$.You can take $a_1$ to be any non-negative integer. Try solving equation 2.