5
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ How about $a_n = n-1$? $\endgroup$ Aug 9, 2019 at 18:24
  • 4
    $\begingroup$ 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. $\endgroup$
    – fleablood
    Aug 9, 2019 at 18:30

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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$ $\endgroup$ Aug 10, 2019 at 7:18
  • $\begingroup$ $@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$ $\endgroup$
    – Jayant Jha
    Aug 10, 2019 at 8:06
  • $\begingroup$ I don't understand how you got to $a_n=a_1-1+\frac{n^2+n}{2}$ please explain $\endgroup$
    – Tyrone
    Aug 10, 2019 at 8:46
  • $\begingroup$ 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. $\endgroup$
    – Jayant Jha
    Aug 10, 2019 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.