Feladat: F.2837 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Battyányi Péter ,  Csörnyei Marianna ,  Egri Ilona ,  Faragó Gergely ,  Futó Gábor ,  Kálmán Tamás ,  Kórász Tamás ,  Kotnyek Balázs ,  Lente Gábor ,  Miklós György ,  Molnár-Sáska Gábor ,  Papolczy Péter ,  Párniczky Benedek ,  Pór Attila ,  Stőhr Lóránt ,  Szentes Balázs ,  Tóth Csaba ,  Ujváry-Menyhárt Zoltán ,  Wiener Gábor 
Füzet: 1991/december, 453 - 454. oldal  PDF file
Témakör(ök): Egyenlőtlenségek, Számsorozatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1991/február: F.2837

Az (an) sorozatot a következőképpen definiáljuk:
an={1  ha  n=0,2a[n2]+3a[n3]+6a[n6],  ha  n1.

Bizonyítsuk be, hogy an10n2+1.

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.

Írjuk fel a definíció alapján a sorozat első néhány elemét:

a0=1;a1=11;a2=31;a3=61;a4=101;a5=101;a6=281;a7=281;a8=361;a9=451;a10=451;a11=451.

Láthatjuk, hogy n=0-ra és n=1-re az állításban szereplő becslés éles, 2n11 esetén viszont nem.
Teljes indukcióval bebizonyítjuk, hogy 2n esetén an102.
Ebből 2n11-re következik az állítás.
Állításunk 2n11 esetén, azaz az előbb felírt elemekre teljesül.
Tegyük fel, hogy N12 olyan szám, hogy 2n<N esetén an10n2 teljesül. Megmutatjuk, hogy akkor aN10N2, vagyis az állításunk n=N esetén is teljesül. A sorozat definíciója szerint
aN=2a[N2]+3a[N3]+6a[N6].

Mivel N12, az [N2], [N3] és [N6] számok 1-nél nagyobbak és N-nél kisebbek, így az indukciós feltevés alapján
a[N2]10[N2]210(N2)2=52N2,

a[N3]10[N3]210(N3)2=109N2,

a[N6]10[N6]210(N6)2=518N2.

Ezekből a becslésekből aN-re azt kapjuk, hogy
aN=2a[N2]+3a[N3]+6a[N6]252N2+3109N2+6518N2=10N2.

Ezzel az állításunkat ‐ és vele együtt a feladat állítását is ‐ bebizonyítottuk.