Problem A. 905. (April 2025)

A. 905. We say that a strictly increasing sequence of positive integers \(\displaystyle n_1\), \(\displaystyle n_2\), \(\displaystyle \ldots\) is non-decelerating if \(\displaystyle n_{k+1}-n_k\le n_{k+2}-n_{k+1}\) holds for all positive integers \(\displaystyle k\). We say that a strictly increasing sequence \(\displaystyle n_1\), \(\displaystyle n_2\), \(\displaystyle \ldots\) is convergence-inducing, if the following statement is true for all real sequences \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle \ldots\): if subsequence \(\displaystyle a_{m+n_1}\), \(\displaystyle a_{m+n_2}\), \(\displaystyle \ldots\) is convergent and tends to 0 for all positive integers \(\displaystyle m\), then sequence \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle \ldots\) is also convergent and tends to 0. Prove that a non-decelerating sequence \(\displaystyle n_1\), \(\displaystyle n_2\), \(\displaystyle \ldots\) is convergence-inducing if and only if sequence \(\displaystyle n_2-n_1\), \(\displaystyle n_3-n_2\), \(\displaystyle \ldots\) is bounded from above.

Proposed by: András Imolay, Budapest

(7 pont)

Deadline expired on May 12, 2025.

First we will prove that if sequence \(\displaystyle n_{i+1}-n_i\) is not bounded from above, then it's not convergence-inducing. For such a sequence we will construct a 0-1 sequence containing an infinite number of 1's such that sequence \(\displaystyle a_{m+n_i}\) is constant 0 from somewhere for every fixed positive integer \(\displaystyle m\). The key to the construction is the following observation: for every pair of positive integers \(\displaystyle m<k\) sequences \(\displaystyle m+n_i\) and \(\displaystyle k+n_i\) share only a finite number of elements. Indeed, \(\displaystyle m+n_i=k+n_j\) implies \(\displaystyle n_i-n_j=k-m>0\), however, since sequence \(\displaystyle n_{i+1}-n_i\) is not bounded and non-decreasing, it means that there exist \(\displaystyle N\) such that \(\displaystyle i>N\) implies \(\displaystyle n_{i+1}-n_i>k-m\). However, this implies that \(\displaystyle n_i-n_j=k-m\) can only occur if both \(\displaystyle i\) and \(\displaystyle j\) are at most \(\displaystyle N+1\), which means that \(\displaystyle i\) can have at most \(\displaystyle N+1\) different values, so the number of common members is also at most \(\displaystyle N+1\). This offers us a simple recursive construction: for \(\displaystyle m=1\), let \(\displaystyle a_{1+n_1}=1\) and \(\displaystyle a_{1+n_i}=0\) if \(\displaystyle i\ge 2\). Now if the values of \(\displaystyle a_{m+n_i}\) are defined for all \(\displaystyle m<M\) and all positive integers \(\displaystyle i\), let's consider sequence \(\displaystyle a_{M+n_i}\): due to our observation, the earlier sequences \(\displaystyle a_{m+n_i}\) (\(\displaystyle m<M\)) share a finite number of members with \(\displaystyle a_{M+n_i}\), therefore there are still infinitely many members of \(\displaystyle a_{M+n_i}\) are undefined: let's define the first of these as 1, and the rest as 0. Those members that were not covered in this construction (in fact, these are only \(\displaystyle a_1\), \(\displaystyle a_2\),..., \(\displaystyle a_{n_1}\)) can be defined as 0.

Now let's prove that if sequence \(\displaystyle n_{i+1}-n_i\) is bounded from above, then it's convergence-inducing. First we give an intuitive argument: it's easy to se that sequence \(\displaystyle n_i\) is arithmetic from somewhere, and this implies that apart from finitely many positive integers the rest can be covered with finitely many translations of sequence \(\displaystyle n_i\) (namely with \(\displaystyle d\) translations, if \(\displaystyle d\) is the common difference of the arithmetic part of the sequence). Therefore, apart from finitely many members, the original sequence \(\displaystyle a_i\) can be covered with sequences \(\displaystyle a_{1+n_i}\), \(\displaystyle a_{2+n_i}\),..., \(\displaystyle a_{d+n_i}\), and since all these go to 0, the original sequence also must go to 0. Now let's see a precise formulation of this argument:

Suppose that \(\displaystyle d\) is the smallest upper bound of sequence \(\displaystyle n_i\). Since sequence \(\displaystyle n_{i+1}-n_i\) is non-decreasing, it means that there exists \(\displaystyle N\) such that \(\displaystyle n_{i+1}-n_i=d\) if \(\displaystyle i\ge N\). Since sequence \(\displaystyle a_{m+n_i}\) goes to 0 (for a fixed \(\displaystyle m\)), therefore for every \(\displaystyle \varepsilon>0\) there exists \(\displaystyle N_m\) such that \(\displaystyle i>N_m\) implies \(\displaystyle |a_{m+n_i}|<0\). Now let's define \(\displaystyle K=\max\{n_N,1+n_{N_1},2+n_{N_2},...,d+n_{N_d}\}\). We claim that \(\displaystyle j>K\) implies \(\displaystyle |a_j|<\varepsilon\). Since \(\displaystyle j>K\ge n_N\), \(\displaystyle j\) can be expressed as \(\displaystyle j=(r+kd)+n_N=r+n_{k+N}\), where \(\displaystyle 1\le r\le d\) and \(\displaystyle k\) is a non-negative integer. Since \(\displaystyle j=r+n_{k+N}>K\ge r+n_{N_r}\) and \(\displaystyle n_i\) is strictly increasing, this implies \(\displaystyle k+N\ge N_r\), and thus by the definition of \(\displaystyle N_r\), \(\displaystyle |a_{r+n_{k+N}}|<\varepsilon\), which we wanted to prove.

Statistics:

19 students sent a solution.
7 points:	Aravin Peter, Balla Ignác , Bodor Mátyás, Czanik Pál, Forrai Boldizsár, Gyenes Károly, Holló Martin, Kocsis 827 Péter, Minh Hoang Tran, Sánta Gergely Péter, Szakács Ábel, Tianyue DAI, Tóth László Pál, Varga Boldizsár, Vödrös Dániel László, Xiaoyi Mo.
5 points:	2 students.
3 points:	1 student.

Problems in Mathematics of KöMaL, April 2025