Feladat: B.3728 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bereczki Péter ,  Birkus Róbert ,  Erdélyi Márton ,  Estélyi István ,  Fehér Gábor ,  Halász Veronika ,  Hubai Tamás ,  Hujter Bálint ,  Jankó Zsuzsanna ,  Kiss-Tóth Christián ,  Komáromy Dani ,  Kovács Péter ,  Molnár András ,  Nagy János ,  Nagy-Baló András ,  Pálinkás Csaba ,  Poronyi Balázs ,  Rácz Miklós ,  Strenner Balázs ,  Szabó Botond ,  Szabó Tamás ,  Vass Márton 
Füzet: 2004/november, 474. oldal  PDF file
Témakör(ök): Rekurzív sorozatok, Racionális számok és tulajdonságaik, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 2004/április: B.3728

Tekintsük azt a sorozatot, amelyre a0=1, továbbá a2n+1=an és a2n+2=an+an+1 teljesül minden n0 egész számra. Bizonyítsuk be, hogy az
{an+1an:n1}={11,12,21,13,32,...}
halmazban valamennyi pozitív racionális szám előfordul.

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. Nyilván elegendő azt bebizonyítani, hogy minden (r;s) relatív prím számpárhoz van olyan n pozitív egész, amelyre an=r és an+1=s. Ezt az állítást az r+s összeg értékére vonatkozó teljes indukcióval igazoljuk.
Ha r+s=2, akkor n=0 megfelelő, ugyanis a0=a1=1. Legyen most k>2 és tegyük fel, hogy a k-nál kisebb összegű relatív prím számpárokra igaz az állítás. Ha az r és s relatív prím számok összege nagyobb 2-nél, akkor nem lehetnek egyenlők: vagy r>s, vagy pedig s>r. Az első esetben tekintsük az (r-s;s) számokat. Ezek relatív prímek, összegük r, amelyre 1<r<k. Az indukciós feltevés szerint tehát van olyan n, amelyre an=r-s és an+1=s. Ekkor a2n+2=r és a2n+3=s. Ugyanígy intézhető el a másik eset, csak a számok sorrendjére kell ügyelnünk: ha s>r, akkor az indukciós feltevés szerint an=r és an+1=s-r teljesül valamilyen n-re, ekkor pedig a2n+1=r és a2n+2=s.