Megoldás. Vegyük észre, hogy az $a_n$ sorozat minden eleme páratlan. Rögzítsük az $n$ értékét és tekintsük a sorozat $a_n$-nel kezdődő elemeinek $a_n$ szerinti maradékait; legyen ez a $b$ sorozat. A sorozat első eleme $b_n$, 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 $b_k=0$. (Ez jelenti azt, hogy $a_k$ osztható $a_n$-nel.)
A $b$ sorozat véges sok értéket vehet fel ($0\le b_i\le a_n-1$), mert értékei az $a_n$ szerinti osztás maradékai. Mivel azonban $b_n$ végtelen sorozat, azért biztosan lesz olyan érték, amelyet végtelen sokszor vesz fel. Tegyük fel, hogy $b_s=b_{s+t}$. A rekurzív képzési szabály miatt az $s$-edik elemtől és az $\left(s+t\right)$-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: $b_s$ a $2b_{s-1}+1$, míg $b_{s+t}$ a $2b_{s+t-1}+1$ elemnek az $a_n$ szerinti maradékával egyenlő. De ha $2b_{s-1}+1$ és $2b_{s+t-1}+1$ ugyanazt a maradékot adja egy páratlan számmal ($a_n$-nel) osztva, akkor $a_n$ osztja a különbségüket: