Let $k\geq 0$ an integer. The sequence $a_0,\ a_1,\ a_2, \ a_3, \ldots$ is defined as follows: $a_0=k$ For $n\geq 1$, we have that $a_n$ is the smallest integer greater than $a_{n-1}$ so that $a_n+a_{n-1}$ is a perfect square. Prove that there are exactly $\left \lfloor{\sqrt{2k}} \right \rfloor$ positive integers that cannot be written as the difference of two elements of such a sequence. Note. If $x$ is a real number, $\left \lfloor{x} \right \rfloor$ denotes the greatest integer smaller or equal than $x$.
Problem
Source: Peruvian IMO TST 2019, P4
Tags: Sequences, floor function, number theory
22.02.2019 03:43
Let $T_k = \frac{k(k+1)}{2}$ denote the $k$th triangular number. The main part is this claim: Lemma: Every positive integer $n$ has a unique representation as $T_m +i$, where $-\left \lfloor \frac m2 \right \rfloor \le i \le \left \lfloor \frac m2 \right \rfloor$. Moreover, $m = \lfloor \sqrt{2n} \rfloor$. Proof: First, verify that every number has a unique representation of that form; this is straightforward. Now we prove that $m =\lfloor \sqrt{2n} \rfloor$ is the desired $m$. It suffices to show that $\left| \frac{m(m+1)}{2} - n \right| \le \left \lfloor \frac m2 \right \rfloor$. Note that $m$ satisfies $m^2 \le 2n$ as well as $(m+1)^2 > 2n$. In particular, this implies $-2m \le m^2 - 2n \le 0$, where equality can hold only if $m$ is even. The desired inequality follows. $\Box$ Suppose $a_0 = k$. Write $m=\lfloor \sqrt{2k} \rfloor$ and $k = T_m + i$. Note that $$a_1 + a_0 > 2a_0 = m(m+1) + 2i \ge m^2.$$So then $a_1+a_0 =(m+1)^2$, and so $a_1 = T_{m+1} - i$. Continuing in this manner, we get $a_2 = T_{m+2} + i$ and $a_3 = T_{m+3} - i$ so on. Define sequence $b_n = a_{n+1} - a_n$. Then we have $b_0 = (m+1) - 2i$ and $b_1 = (m+2) + 2i$ and $b_2 = (m+3) - 2i$ and so on. In particular $b_{n+2} = b_n + 2$. Let $B = \min(b_0, b_1)$. Since $b_0, b_1$ have different parity, we see that the $b_n$ cover all differences except $1, 2, \dots, B-1$, and $B + 1, B+3, \dots, \max(b_0, b_1) - 1$. It is straightforward to check that this comprises $m$ numbers which cannot be written as differences of the $a_n$, so we are done. $\Box$