 Felhasználjuk, hogy egy pozitív egész szám 3-as maradéka megegyezik számjegyei összegének 3-as maradékával. Legyen A(n,k) (k=0,1,2) azon n-jegyű számok halmaza, melyek a 2,3,7,9 számjegyekből állnak és 3-mal osztva k-t adnak maradékul. Legyen továbbá an,k=|A(n,k)|. Vegyük észre, hogy an,1=an,2 teljesül, mert ha x A(n,1) és x számjegyeiben kicseréljük a ketteseket hetesre és viszont, akkor A(n,2)-beli számot kapunk és ez a megfeleltetés kölcsönösen egyértelmű. Másrészt nyilván
an,0+an,1+an,2=4n, azaz az előbbiek szerint
Írjunk fel egy rekurziót aszerint, hogy egy A(n,k)-beli szám utolsó számjegye 2,3,7, vagy 9. Ekkor
| an,0=an-1,1+an-1,0+an-1,2+an-1,0=2an-1,0+2an-1,1 | (2) |
| an,1=an-1,2+an-1,1+an-1,0+an-1,1=an-1,0+3an-1,1 | (3) |
Véve a (2)-(3) különbséget
an,0-an,1=an-1,0-an-1,1=...=a1,0-a1,1=2-1=1
Tehát felhasználva (1)-et
an,0+2(an,0-1)=4n
|