Feladat: B.3695 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Filus Tamás ,  Kirilly György 
Füzet: 2004/szeptember, 347 - 348. oldal  PDF file
Témakör(ök): Exponenciális egyenletek, Teljes indukció módszere, Binomiális együtthatók, Feladat
Hivatkozás(ok):Feladatok: 2004/január: B.3695

Legyen az n pozitív egész szám. Igazoljuk, hogy 5n-8n2+4n-1 osztható 64-gyel.

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.

I. megoldás. Bizonyítsuk az állítást n-re vonatkozó teljes indukcióval.
Az n=1 esetén 5n-8n2+4n-1=5-8+4-1=0 és 640. Az állítás igaz.
Tegyük fel, hogy valamilyen n természetes számra teljesül az állítás. A kifejezés értéke (n+1)-re:

5n+1-8(n+1)2+4(n+1)-1=55n-8(n2+2n+1)+4n+4-1==55n-8n2-16n-8+4n+4-1=55n-8n2-12n-5==5(5n-8n2+4n-1)+32n2-32n=5(5n-8n2+4n-1)+32n(n-1).
Az 5n-8n2+4n-1 az indukciós feltevés szerint osztható 64-gyel, ezért ennek ötszöröse is osztható 64-gyel. A 32n(n-1) is osztható 64-gyel, hiszen két egymást követő természetes szám (n-1 és n) valamelyike biztosan páros, így a 32-szerese osztható 64-gyel. Ha két 64-gyel osztható számot összeadunk, akkor az összegük is osztható 64-gyel, tehát (n+1)-re is igaz az állítás.
Ezzel minden n pozitív egészre beláttuk, hogy 5n-8n2+4n-1 osztható 64-gyel.
 
II. megoldás. Ha n=1, akkor az első megoldás behelyettesítése szerint az állítás igaz. Legyen az n legalább 2 és az 5n-8n2+4n-1 kifejezés első tagját írjuk fel úgy, mint két tag összegének hatványát: (4+1)n. A binomiális tétel alapján ekkor
5n-8n2+4n-1=4n+(n1)4n-1+...++(nn-3)43+(nn-2)42+(nn-1)4+1-8n2+4n-1.


Mivel az első n-2 tag mindegyikében a 4 kitevője legalább 3 és 43=64, ezek a tagok oszthatók 64-gyel. Ezeken kívül pedig
(nn-2)=(n2)és(nn-1)=(n1),
ezért
(nn-2)42+(nn-1)4+1-8n2+4n-1==(n2)42+(n1)4+1-8n2+4n-1==n(n-1)216+4n+1-8n2+4n-1=8n2-8n+4n+1-8n2+4n-1=0,


ami szintén osztható 64-gyel. Ez azt jelenti, hogy 5n-8n2+4n-1 előáll 64-gyel osztható számok összegeként, ezért osztható 64-gyel.