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

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

• How about $a_n = n-1$? Aug 9, 2019 at 18:24
• The very start that $a_2|a_1 + 2$ but $a_2 > a_1$ Leaves very few choices. $a_1 < a_2 \le a_1 + 2$ so $a_2 = a_1 + 1$ or $a_2=a_1 + 2$. If $a_2 = a_1 + 1$ then $a_2|a_2 +1$ which is only possible for $a_2 = 1$. So $a_1 = 0$ and $a_2=1$. And if $a_2=a_1 + 2$ then we have $a_3|a_2 + 3$ but we have $a_3=a_2+1,a_2+2,a_2+3$ and $a_2|a_2+1$ is impossible $a_3=a_2+2$ is only possible if $a_2 = 2$ and $a_0=0$ and $a_3= a_2+3$ is only possible if $a_2=3$ and $a_1 = 1$. And so on. Aug 9, 2019 at 18:30

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.

• It is not true that $a_n = a_{n-1} + n$ is the only solution, as shown in Interstellar's comment : there's also $a_n=n-1$ Aug 10, 2019 at 7:18
• $@EwanDelanoy$ Thanks. I spotted a small mistake in my solution and I have edited it. The case provided by interstellar will be included in $2a_n=a_{n-1}+n$ Aug 10, 2019 at 8:06
• I don't understand how you got to $a_n=a_1-1+\frac{n^2+n}{2}$ please explain Aug 10, 2019 at 8:46
• We know that $a_n-a_{n-1}=n$, sigma it up from i=2 to i=n. All the terms will get cancelled and the solution given will remain. I will edit my answer later for you. Aug 10, 2019 at 11:40