Ta sẽ chứng minh bằng quy nạp.
Với $n = 1$, ta có
$4^1 + 15.1 - 1 = 18 $ chia hết cho $9$
Giả sử khẳng định đúng đến $k = n$. Ta sẽ chứng minh nó đúng với $k = n+1$
Thật vậy, với $k = n +1$ ta có
$4^{n+1} + 15(n+1) - 1 = 4.4^n + 15n + 15 - 1$
$= 4(4^n + 15n - 1) -45n +18$
$= 4(4^n + 15n - 1) - 9(5n-2)$
Theo giả thiết quy nạp ta có $4^n + 15n - 1$ chia hết cho 9 và hiển nhiên $9(5n-2)$ chia hết cho 9.
Vậy $4^{n+1} + 15(n+1) - 1$ chia hết cho 9. Vậy ta hoàn thành bước chứng minh quy nạp và có điều phải chứng minh.
