Jelölje $G_n$ azt az irányított gráfot, amelynek a csúcsai $A_0$, $A_1$, $\text{...}$, $A_n$, az élei pedig: $A_i$-ből $A_{i+2}$-be megy egy él, $A_i$-ből $A_{i+3}$-ba pedig $1998$ darab él megy, minden szóbajövő $i$ esetére. Jelölje az $\overrightarrow{A_0{A}_n}$ irányított utak számát $b_n$.
Látható, hogy $a_2=b_0=1$, $a_3=b_1=0$, $a_4=b_2=1$. Legyen a továbbiakban $n\ge 3$. Ekkor $A_n$-be el lehet jutni (irányított út mentén) $A_{n-2}$-ből egyféleképpen, $A_{n-3}$-ból pedig 1998-féleképpen. Mivel minden $\overrightarrow{A_0{A}_n}$ útnak érintenie kell $A_{n-2}$-t vagy $A_{n-3}$-at, így $b_n=b_{n-2}+1998b_{n-3}$; tehát $b_n=a_{n+2}$. Ezek szerint a $b_{2n-3}=2b_{n-1}{b}_{n-2}+1998b_{n-3}^2$ összefüggést kell igazolni.
Az $A_{2n-3}$-ba vezető utak a következők lehetnek:
a) $A_{n-1}$-en keresztül menő;
b) $A_{n-2}$-n keresztül menő;
c) sem $A_{n-1}$-et, sem $A_{n-2}$-t nem érintő.

Nyilván minden út e három fajta közül pontosan az egyikbe tartozik. Az a), ill. b) típus nyilván $b_{n-1}{b}_{n-2}$, ill. $b_{n-2}{b}_{n-1}$ utat tartalmaz. Ha egy út c)-típusú, akkor át kell haladnia $A_{n-3}$-on és $A_n$-en is; az ilyen utak száma ezért $b_{n-3}\cdot 1998\cdot b_{n-3}$. Tehát $b_{2n-3}=b_{n-1}{b}_{n-2}+b_{n-2}{b}_{n-1}+b_{n-3}\cdot 1998\cdot b_{n-3}$, ami éppen a feladat állítása.