Feladat: F.2964 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csergőffy Tibor ,  Csörnyei Marianna ,  Dőtsch András ,  Gyarmati Katalin ,  Horváth Gábor ,  Imreh Csanád ,  K. L. ,  Maróti Gábor ,  Megyesi Zoltán ,  Pete Gábor ,  Tóth Zoltán 
Füzet: 1994/április, 197 - 198. oldal  PDF file
Témakör(ök): Indirekt bizonyítási mód, Teljes indukció módszere, Rekurzív sorozatok, Sorozatok monotonitása, korlátossága, Függvények monotonitása, Feladat
Hivatkozás(ok):Feladatok: 1993/május: F.2964

Bizonyítsuk be, hogy ha f az egész számegyenesen értelmezett, pozitív értékű, monoton növekvő függvény, akkor létezik olyan a szám, amelyre
f(a+1f(a))<2f(a).(5)

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Tegyük fel, hogy nem igaz a feladat állítása, vagyis minden a valós számra

f(a+1f(a))2f(a).
Definiáljuk az a0,a1,... sorozatot a következő rekurzióval:
a0=0,an+1=an+1f(an).

Az indirekt feltevés alapján a tetszőleges n nemnegatív egész számra:
f(an+1)=f(an+1f(an))2f(an);
ebből n szerinti indukcióval azt kapjuk, hogy
f(an)2nf(a0).
Megmutatjuk viszont, hogy az {an} sorozat felülről korlátos. A rekurziót és (1)-et felhasználva:

an=an-a0=(a1-a0)+(a2-a1)+(a3-a2)+...+(an-an-1)==1f(a0)+1f(a1)+1f(a2)+...+1f(an-1)1f(a0)+12f(a0)+14f(a0)+...+12n-1f(a0)==1f(a0)(1+12+14+...+12n-1).

Mivel 1+12+14+...+12n-1=2-12n-1<2, azért az
an1f(a0)(1+12+14+...+12n-1)<2f(a0).

Az {an} sorozatnak tehát minden eleme kisebb, mint 2f(a0), a sorozat felülről korlátos.

Legyen b=2f(a0). Mivel az f függvény monoton nő, és minden n0 egészre an<b,
f(an)f(b).(
Ha most összevetjük (1)-et és (2)-t, ellentmondásra jutunk:
2nf(a0)f(an)f(b),2nf(b)f(a0).

Ez az egyenlőtlenség azt állítja, hogy minden 2-hatvány kisebb vagy egyenlő, mint f(b)f(a0), ami lehetetlen.
Az indirekt feltevésből ellentmondásra jutottunk, tehát az állítás igaz.