Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 741. feladat (2019. január)

A. 741. Legyen \(\displaystyle f\) olyan pozitív egészeken értelmezett függvény, melyre \(\displaystyle f(n)\ge 0\) és \(\displaystyle f(n)\le f(n+1)\) minden \(\displaystyle n\)-re. Igazoljuk, hogy ha

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

divergens, akkor létezik olyan \(\displaystyle a_1,a_2,\dots\) sorozat, amelyre \(\displaystyle \frac{a_n}{n}\) felvesz minden racionális számot értékként, míg

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

teljesül minden \(\displaystyle n\), \(\displaystyle m\) párra.

Schweitzer-feladat nyomán

(7 pont)

A beküldési határidő 2019. február 11-én LEJÁRT.


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

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

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

\(\displaystyle \frac{a_n}{n}\le c_m,\qquad \text{ha }1\le n\le 2^m.\)\(\displaystyle (1)\)

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

\(\displaystyle \frac{f(2^{m+1})}{2^m}\le 8\sum_{x\in I_{m+2}}\frac{f(x)}{x^2}.\)\(\displaystyle (2)\)

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!


Statisztika:

Az A. 741. feladat értékelése még nem fejeződött be.


A KöMaL 2019. januári matematika feladatai