Feladat: B.3649 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Ablonczy Dávid ,  Backhausz Ágnes ,  Bartha Emőke ,  Czank Tamás ,  Farkas Balázs ,  Fehér Gábor ,  Filus Tamás ,  Füredi Mihály ,  Gehér György ,  Gidófalvy Kitti ,  Gyarmati Ákos ,  Hubai Tamás ,  Jankó Zsuzsanna ,  Jelitai Kálmán ,  Juhász Máté Lehel ,  Kiss-Tóth Christián ,  Koreck Péter ,  Kormányos Balázs ,  Korotij Ágnes ,  Kórus Péter ,  Mánfay Máté ,  Mátyás Péter ,  Molnár András ,  Pongrácz András ,  Poronyi Balázs ,  Ruppert László Gábor ,  Salát Máté ,  Simon Balázs ,  Szabó Botond ,  Szalai Attila ,  Tábor Áron ,  Torma Róbert ,  Vaskó Richárd 
Füzet: 2004/május, 277. oldal  PDF file
Témakör(ök): Rekurzív sorozatok, Oszthatóság, Feladat
Hivatkozás(ok):Feladatok: 2003/május: B.3649

Legyen a0=5 és an+1=2an+1. Bizonyítsuk be, hogy minden n természetes számhoz létezik tőle különböző k, hogy anak.

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.

Megoldás. Vegyük észre, hogy az an sorozat minden eleme páratlan. Rögzítsük az n értékét és tekintsük a sorozat an-nel kezdődő elemeinek an szerinti maradékait; legyen ez a b sorozat. A sorozat első eleme bn, ami nyilván 0.
Azt kell bebizonyítanunk, hogy létezik olyan n-től különböző k, amelyre szintén igaz, hogy bk=0. (Ez jelenti azt, hogy ak osztható an-nel.)
A b sorozat véges sok értéket vehet fel (0bian-1), mert értékei az an szerinti osztás maradékai. Mivel azonban bn végtelen sorozat, azért biztosan lesz olyan érték, amelyet végtelen sokszor vesz fel. Tegyük fel, hogy bs=bs+t. A rekurzív képzési szabály miatt az s-edik elemtől és az (s+t)-edik elemtől a maradékok ugyanúgy folytatódnak, tehát a b sorozat az s indextől kezdve biztosan periodikus. Ettől azonban még nem lenne feltétlenül szükséges, hogy ebben a periódusban szerepeljen a 0 maradék.
Vizsgáljuk visszafelé a maradékokat: bs a 2bs-1+1, míg bs+t a 2bs+t-1+1 elemnek az an szerinti maradékával egyenlő. De ha 2bs-1+1 és 2bs+t-1+1 ugyanazt a maradékot adja egy páratlan számmal (an-nel) osztva, akkor an osztja a különbségüket:

an2(bs+t-1-bs-1).
Az an páratlan lévén, an(bs+t-1-bs-1), tehát ugyanazt a maradékot adják an-nel osztva, azaz bs-1=bs+t-1.
Ez azt jelenti, hogy bs-től visszafelé is periodikusak a maradékok egészen bn-ig, vagyis a 0 is végtelen sokszor ismétlődő maradék.