• Với $n=1$: $4^1+15\cdot1-1=18$ chia hết cho $9$.
• Giả sử $4^k+15k-1$ chia hết cho $9$, với $k\geq1$.
  Ta sẽ chứng minh $4^{k+1}+15(k+1)-1$ cũng chia hết cho $9$.
• Thật vậy,
  $\begin{aligned}
  4^{k+1}+15(k+1)-1&=4\cdot4^k+15k+14\\
  &=4\cdot4^k+60k-45k+18-4\\
  &=4\left(4^k+15k-1\right)+18-45k\\
  &=4\left(4^k+15k-1\right)+9(2-5k).
  \end{aligned}$
  Suy ra $4^{k+1}+15(k+1)-1$ chia hết cho $9$.

Vậy $4^n+15n-1$ chia hết cho $9$, $\forall n\in\mathbb{N}^*$.