Nézzük, hogy n=1-re mi a helyzet:

4¹ + 15*1 - 1 = 18, ami osztható 9-cel.

Tegyük fel, hogy n-ig igaz az állítás. Nézzük, hogy mi a helyzet n-1-re:

4n+1 + 15*(n+1) - 1 = 4*4ⁿ + 15n + 15 - 1

Ezt rendezzük úgy, hogy a fenti kifejezés megjelenjen, mivel arról tudjuk, hogy osztható 9-cel:

3*4ⁿ + 15 + [4ⁿ + 15n -1]

A []-ben kévő kifejezés az indukciós feltevés miatt osztható 9-cel. Már csak azt kell belátni, hogy a 3*4ⁿ+15 osztható 9-cel. Ezt is csinálhatjuk teljes indukcióval;

n=1 esetén 3*4¹ + 15 =27, ez jó.
n=2 esetén 3*4² + 15 = 63, ez is.

Akkor nézzük meg, hogy n+1-re mi a helyzet:

3*4n+1+15 = 3*4*4ⁿ + 15 = 12*4ⁿ + 15 = 9*4ⁿ + [3*4ⁿ + 15]

Ismét az indukciós feltevés miatt a []-ben lévő rész osztahtó 9-cel, a másik tag pedig ránézésre osztható 9-cel, mivel (9*4ⁿ)/9=4ⁿ. Q. E. D.