Megoldás. Nyilván elegendő azt bebizonyítani, hogy minden $\left(r;s\right)$ relatív prím számpárhoz van olyan $n$ pozitív egész, amelyre $a_n=r$ és $a_{n+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 $a_0=a_1=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 $\left(r-s;s\right)$ 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 $a_n=r-s$ és $a_{n+1}=s$. Ekkor $a_{2n+2}=r$ és $a_{2n+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 $a_n=r$ és $a_{n+1}=s-r$ teljesül valamilyen $n$-re, ekkor pedig $a_{2n+1}=r$ és $a_{2n+2}=s$.