Problem A. 741. (January 2019)

A. 741. Let \(\displaystyle f\) be a function defined on the positive integers with \(\displaystyle f(n)\ge 0\) and \(\displaystyle f(n)\le f(n+1)\) for all \(\displaystyle n\). Prove that if

\(\displaystyle \sum\limits_{n=1}^\infty \frac{f(n)}{n^2}\)

diverges, there exists a sequence \(\displaystyle a_1,a_2,\dots\) such that the sequence \(\displaystyle \frac{a_n}{n}\) hits every rational number, while

\(\displaystyle a_{n+m}\le a_n+a_m+f(n+m)\)

holds for every pair \(\displaystyle n\), \(\displaystyle m\).

Based on a problem of the Miklós Schweitzer competition

(7 pont)

Deadline expired on February 11, 2019.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Az alábbi egyenlőtlenséget kell teljesítenünk:

Legyen \(\displaystyle g(n)=\sum_{1}^n \frac{f(k)}{k^2}\) a részletösszegek sorozata. A feltétel szerint \(\displaystyle g\) tetszőlegesen nagy értéket felvesz. Legyen most

\(\displaystyle b_n=n\cdot g(n)-C\cdot n\)

minden \(\displaystyle n\)-re.

Állítás. A \(\displaystyle (b_n)\) sorozat teljesíti \(\displaystyle (*)\)-ot.

Bizonyítás. A bal oldalon \(\displaystyle (n+m)-n-m=0\) miatt a \(\displaystyle Cn\)-es tagok kiesnek, így

\(\displaystyle b_{n+m}-b_n-b_m=\left((n+m)\sum_1^{n+m} \frac{f(k)}{k^2}-n\sum_1^n \frac{f(k)}{k^2}-m\sum_1^m \frac{f(k)}{k^2}\right)=\)

\(\displaystyle =\left(n\sum_{n+1}^{n+m}\frac{f(k)}{k^2}+m\sum_{m+1}^{m+n}\frac{f(k)}{k^2}\right)\le f(n+m)\cdot \left(n\sum_{n+1}^{n+m}\frac{1}{k^2}+m\sum_{m+1}^{m+n}\frac{1}{k^2}\right),\)

ahol felhasználtuk, hogy \(\displaystyle f\) nem csökkenő. Világos, hogy \(\displaystyle \frac1{k^2}\le \frac1{k(k-1)}=\frac1{k-1}-\frac1k\), ahol \(\displaystyle k\ge 2\), ahonnan

\(\displaystyle \sum_{n+1}^{n+m}\frac1{k^2}\le \sum_{n+1}^{n+m}\left(\frac1{k-1}-\frac1{k}\right)=\frac1n-\frac1{n+m},\)

s így a zárójelben álló összeg

\(\displaystyle <n\left(\frac1n-\frac1{n+m}\right)+m\left(\frac1m-\frac1{m+n}\right)=1,\)

tehát valóban \(\displaystyle b_{n+m}-b_n-b_m<f(n+m)\). \(\displaystyle \blacksquare\)

A befejezéshez soroljuk fel a racionális számokat: \(\displaystyle q_1,q_2,\dots\). Az \(\displaystyle (a_n)\) sorozat megadásához különböző \(\displaystyle C\) értékekhez tartozó \(\displaystyle (b_n)\) sorozatokat fogunk egymás után írni. Tegyük fel, hogy \(\displaystyle a_1,a_2,\dots,a_N\)-et már megadtuk úgy, hogy \(\displaystyle (*)\) fennállása mellett már \(\displaystyle i=1,2,\dots,k-1\) esetén \(\displaystyle \frac{a_{n_i}}{n_i}=q_i\) valamilyen \(\displaystyle n_i\)-re. Ekkor amennyiben valamilyen \(\displaystyle C\)-vel \(\displaystyle (b_n)\)-re fennáll, hogy

\(\displaystyle a_1\ge b_1,a_2\ge b_2,\dots,a_N\ge b_N,\qquad \text{illetve } \frac{b_{n_k}}{n_k}=q_k\text{ valamely }N<n_k\text{-ra},\)

akkor mivel \(\displaystyle (b_n)\)-re teljesül a \(\displaystyle (*)\), azért \(\displaystyle (a_n)\)-re is teljesülni fog, ha \(\displaystyle (a_{N+1},\dots,a_{n_k}):=(b_N,\dots,b_{n_k})\), hiszen \(\displaystyle (*)\) bal oldala a szükséges esetekben csökken, mikor \(\displaystyle b_n\)-et megnöveljük \(\displaystyle a_n\)-re. Ez \(\displaystyle C=q_k-g(n_k)\) választással és elég nagy \(\displaystyle n_k>N\) mellett biztosítható, mert \(\displaystyle g(n)\) tetszőlegesen nagy értéket felvesz. Ily módon rekurzívan megadhatjuk a kívánt \(\displaystyle (a_n)\) sorozatot.

Megjegyzés. Legyen \(\displaystyle a_1,a_2,\dots\) egy \(\displaystyle (*)\)-ot teljesítő sorozat, ahol \(\displaystyle \sum \frac{f(n)}{n^2}\) konvergens. Ekkor Erdős és De Bruijn tétele, hogy \(\displaystyle \frac{a_n}{n}\) konvergens, vagy \(\displaystyle \frac{a_n}{n}\to -\infty\). Alább vázoljuk a tétel bizonyítását.

1. lépés. Belátjuk, hogy az \(\displaystyle \frac{a_n}{n}\) sorozat felülről korlátos.

Bizonyítás. Ha \(\displaystyle f\) azonosan nulla lenne, teljes indukcióval \(\displaystyle a_n\le na_1\), így kész. (Világos, hogy indukcióval tudunk majd bizonyítani.) A feltételben a további \(\displaystyle f(n+m)\) tagok hatására azonban ahogy \(\displaystyle n\) növekszik, az \(\displaystyle \frac{a_n}{n}\)-re adható felső becslések egyre növekedni fognak. A \(\displaystyle \sum_{x=1}^N \frac{f(x)}{x^2}\) összegek korlátosságával fogjuk belátni, hogy ezek a felső becslések korlátosak.

A következő technikát használjuk. Legyen \(\displaystyle m=1,2,\dots\)-ra \(\displaystyle I_m=(2^m,2^{m+1}]\cap \mathbb{Z}\). Ekkor az \(\displaystyle I_m\) intervallumok uniója \(\displaystyle (2;\infty)\).

Tegyük fel, hogy \(\displaystyle c_m\) olyan, hogy

Legyen \(\displaystyle n\in I_{m+1}\), és \(\displaystyle k+l=n\). Mondjuk legyen \(\displaystyle \{k,l\}=\{n/2,n/2\}\) ha \(\displaystyle n\) páros és \(\displaystyle \{(n-1)/2,(n+1)/2\}\) ha \(\displaystyle n\) páratlan. Ekkor \(\displaystyle 1\le k,l\le 2^m\), s így

\(\displaystyle a_n\le a_k+a_l+f(n)\le kc_m+lc_m+f(n)=nc_m+f(n),\)

ahonnan

\(\displaystyle \frac{a_n}{n}\le c_m+\frac{f(n)}{n}\le c_m+\frac{f(2^{m+1})}{2^m}.\)

Ha tehát úgy definiáljuk a \(\displaystyle c_1,c_2,\dots\) sorozatot, hogy \(\displaystyle c_1=\max_{n=1,2,3,4}\frac{a_n}{n}\) és

\(\displaystyle c_{m+1}=c_m+\frac{f(2^{m+1})}{2^m},\)

akkor \(\displaystyle (1)\) minden \(\displaystyle m\)-re fennáll.

Mivel pedig

\(\displaystyle 2^{m+1}f(2^{m+1})\le \sum_{x\in I_{m+2}} f(x)=\sum_{x\in I_{m+2}}x^2\cdot \frac{f(x)}{x^2}\le 2^{2m+4}\sum_{x\in I_{m+2}}\frac{f(x)}{x^2},\)

ezért

Innen indukcióval minden \(\displaystyle m>1\)-re

\(\displaystyle c_m\le c_1+\sum_{\mu=1}^{m-1} \sum_{x\in I_{\mu+2}}\frac{f(x)}{x^2}=c_1+\sum_{x=9}^{2^{x+2}}\frac{f(x)}{x^2}.\)

Mivel pedig utóbbi részletösszegek korlátosak, így a \(\displaystyle c_m\) sorozatnak van \(\displaystyle C\) felső korlátja. Ekkor pedig \(\displaystyle \frac{a_n}{n}\le C\) minden \(\displaystyle n\)-re. \(\displaystyle \blacksquare\)

2. lépés. A limsup-ötlettel átfogalmazzuk a bizonyítandót.

Mivel \(\displaystyle \frac{a_n}{n}\) felülről korlátos, ezért \(\displaystyle \sigma_N=\sup_{n\ge N}\frac{a_n}{n}\) minden \(\displaystyle N\)-re létezik, s mivel \(\displaystyle (\sigma_N)\) monoton csökkenő, ezért ha alulról korlátos, akkor konvergál egy \(\displaystyle L\) határértékhez, s egyébként a sorozat \(\displaystyle \to -\infty\), s ezzel \(\displaystyle \frac{a_N}{N}\le \sigma_N\) miatt \(\displaystyle \frac{a_N}{N}\to-\infty\) is teljesül (mint a rendőrelvhez hasonlóan ellenőrizhető). A tétel belátásához tehát elég azzal az esettel foglalkoznunk, hogy

\(\displaystyle \sigma_N\to L.\)

Ebből következik, hogy:

• adott \(\displaystyle \varepsilon>0\)-ra majdnem minden \(\displaystyle n\)-re (mondjuk \(\displaystyle n\ge N(\varepsilon)\)-ra) \(\displaystyle \sigma_n\le L+\varepsilon\),
• adott \(\displaystyle \delta>0\)-ra nem lehet, hogy az \(\displaystyle \frac{a_n}{n}\) sorozat \(\displaystyle n\ge N\)-re mindig \(\displaystyle \le L-\delta\), hisz akkor \(\displaystyle \sigma_n\le L-\delta\) minden \(\displaystyle n\ge N\)-re, s így \(\displaystyle |\sigma_n-L|<\delta\) csak véges sok \(\displaystyle n\)-re teljesül; tehát \(\displaystyle \frac{a_n}{n}>L-\delta\) végtelen sok \(\displaystyle n\)-re.
• Elég tehát belátni, hogy minden \(\displaystyle \delta>0\)-ra \(\displaystyle \frac{a_n}{n}>L-\delta\) majdnem minden \(\displaystyle n\)-re.

Tegyük fel indirekt, hogy valamilyen \(\displaystyle \delta>0\)-ra \(\displaystyle \frac{a_n}{n}\le L-\delta\) végtelen sok \(\displaystyle n\)-re. Ezekből a tagokból kiindulva adunk felső becslést a későbbi tagokra; ha mondjuk \(\displaystyle \frac{a_n}{n}\le L-\frac1{16}\delta\) lesz minden elég nagy \(\displaystyle n\)-re, az a fentiek szerint ellentmondás.

3. lépés. Mondjuk egy olyan \(\displaystyle q\)-ból kiindulva, melyre \(\displaystyle \frac{a_q}{q}\le L-\delta\), felső becslést adunk minden \(\displaystyle a_n\)-re. Az 1. lépéshez némileg hasonlóan járunk el.

Először vizsgáljuk azokat a tagokat, amiket csak \(\displaystyle a_q\) segítségével tudunk becsülni: \(\displaystyle a_{2q}\le a_q+a_q+f(2q)\), \(\displaystyle a_{3q}\le a_q+a_{2q}+f(3q)\), stb. Némi próbálkozás után világossá válik, hogy a következő ötlet teszi legerősebbé a becslést:

\(\displaystyle a_{2^kq}\le a_{2^{k-1}q}\cdot 2+f(2^kq).\)

A \(\displaystyle \sum\frac{f(x)}{x^2}\) sorral kapcsolatba hozva:

\(\displaystyle 2^kq\cdot f(2^kq)\le f(2^kq+1)+\dots +f(2^{k+1}q)\le \)

\(\displaystyle \le (2^{k+1}q)^2\cdot \left[\frac{f(2^kq+1)}{(2^kq+1)^2}+\dots +\frac{f(2^{k+1}q)}{(2^{k+1}q)^2}\right],\)

ahonnan

\(\displaystyle \frac{a_{2^kq}}{2^kq}\le \frac{a_{2^{k-1}q}}{2^{k-1}q}+4\cdot \left[\frac{f(2^kq+1)}{(2^kq+1)^2}+\dots +\frac{f(2^{k+1}q)}{(2^{k+1}q)^2}\right],\)

s így indukcióval kapjuk, hogy

\(\displaystyle \frac{a_{2^kq}}{2^kq}\le \frac{a_q}{q}+\sum_{x=q+1}^{2^{k+1}q}\frac{f(x)}{x^2}.\)

Tehát ha \(\displaystyle \frac{a_q}{q}\le L-\delta\), akkor minden \(\displaystyle k=0,1,2,\dots\) esetén

\(\displaystyle \frac{a_{2^kq}}{2^kq}\le (L-\delta)+\sum_{x>q}\frac{f(x)}{x^2}.\)

Ha elég nagy \(\displaystyle q\)-ból indulunk ki, akkor \(\displaystyle \sum_{x>q}\frac{f(x)}{x^2}\le \frac12\delta\) (ezt könnyű ellenőrizni), s így kapjuk:

\(\displaystyle \frac{a_{2^kq}}{2^kq}\le L-\frac12\delta.\)

Következő lépésünk: tegyük fel, hogy \(\displaystyle \frac{a_n}{n}\le L-\frac12\delta\) (mint \(\displaystyle n=2^kq\)), illetve hogy \(\displaystyle \frac{a_{m-n}}{m-n}\le L+\varepsilon\) (ez \(\displaystyle m-n\ge N(\varepsilon)\)-ra igaz). Ekkor:

\(\displaystyle a_{m}\le n(L-\frac12\delta)+(m-n)(L+\varepsilon)+f(m),\)

\(\displaystyle \frac{a_{m}}{m}\le L-\frac{n}{m}\cdot \frac12\delta+\frac{m-n}{m}\varepsilon+\frac{f(m)}{m}.\)

Gondoljuk meg \(\displaystyle (2)\)-ből, hogy \(\displaystyle \lim_{\mu\to \infty}\frac{f(\mu)}{\mu}=0\). Tegyük fel, hogy \(\displaystyle \frac{f(m)}{m}\le \varepsilon\).

Éljünk az \(\displaystyle \varepsilon=\frac1{64}\delta\) választással. Tegyük fel, hogy \(\displaystyle n=2^kq\) elég nagy ahhoz, hogy mindkét említett becslés teljesüljön, ha \(\displaystyle m\in (2n,4n]\). Ekkor

\(\displaystyle \frac{a_m}{m}\le L-\frac14\cdot \frac12\delta+1\cdot \frac1{64}\delta+\frac1{64}\delta\le L-\frac1{16}\delta.\)

Tehát ha \(\displaystyle k\) elég nagy, mondjuk ha \(\displaystyle k\ge K\), akkor \(\displaystyle m\in (2^{k+1}q,2^{k+2}q]\)-ra

\(\displaystyle \frac{a_m}{m}\le L-\frac1{16}\delta.\)

Ezért ez minden \(\displaystyle m>2^{K+1}q\) esetén fennáll. Meg is kaptuk kívánt ellentmondásunkat, így készen vagyunk!

Statistics:

2 students sent a solution.
7 points:	Schrettner Jakab.
0 point:	1 student.

Problems in Mathematics of KöMaL, January 2019