Let $d$ be a positive integer. The seqeunce $a_1, a_2, a_3,...$ of positive integers is defined by $a_1 = 1$ and $a_{n + 1} = n\left \lfloor \frac{a_n}{n} \right \rfloor+ d$ for $n = 1,2,3, ...$ . Prove that there exists a positive integer $N$ so that the terms $a_N,a_{N + 1}, a_{N + 2},...$ form an arithmetic progression. Note: If $x$ is a real number, $\left \lfloor x \right \rfloor $ denotes the largest integer that is less than or equal to $x$.
Problem
Source: Peru IMO TST 2018 p5
Tags: arithmetic sequence, floor function, recurrence relation, algebra, function
15.05.2019 01:56
Let $b_n = nd - a_n.$ Observe that the condition of the problem gives us that $$b_{n+1} = nd + d - n \left \lfloor \frac{a_n}{n} \right \rfloor - d = nd - n \left \lfloor \frac{a_n}{n} \right \rfloor = n( d - \left \lfloor \frac{a_n}{n} \right \rfloor),$$which implies that $\frac{b_{n+1}}{n} = \left \lceil \frac{b_n}{n} \right \rceil.$ Let's now define the sequence $c_n$ by $c_n = \frac{b_{n+1}}{n} \forall n \in \mathbb{N},$ which we know from the above is integral. Then, we have that $$c_{n+1} = \frac{b_{n+2}}{n+1} = \left \lceil \frac{b_{n+1}}{n+1} \right \rceil \le \left \lceil \frac{b_{n+1}}{n} \right \rceil = c_n,$$so that the sequence $\{c_i\}$ is nonincreasing. Therefore, as it's a positive integer sequence, it's eventually constant, say $c_n = C$ for $n \ge N.$ Then, for $n > N$, we have that $b_n = (n-1)C \Rightarrow a_n = nd - b_n = nd - (n-1)C = n(d-C) + C,$ which is clearly arithmetic, as desired. $\square$
19.10.2022 00:29
First of all, see that $a_n\leq nd$, for all $n$. See that if $a_{n+1}=nq+d$ for some $q\leq d$ and big $n$, we get: $$a_{n+2}=(n+1)\left\lfloor\frac{nq+d}{n+1}\right\rfloor+d=(n+1)q+d,$$and it follows by a simple induction that the sequence will be an arithmetic progression. Now we prove that the desired $a_n$ exists by taking a large $n$ (bigger than $d$), and let $a_n=qn+r$, with $0\leq r<n$. See that $q\leq d$ since $a_n\leq nd$ and $$a_{n+1}=n\left\lfloor q+\frac{r}{n}\right\rfloor+d=nq+d,$$as desired. $\blacksquare$
20.10.2024 18:06
For the record, this is a little modification of problem 10.4 from 2008 Russian Zonal olympiad (which has little chance of appearing here, since the contest is now discontinued).