Với n=1n=1, ta có

4^1+15.1−1=18chia 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−1chia 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)−1chia 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.