Show that$4^n-3n-1$ is divisible by “9”.

Let $s\left(n\right)$ be a statement $4^n-3n-1$is divisible by 9

step-1: If $n=1$

since $4^1-3\left(1\right)-1=0=9\times 0$ is divisble by 9

$\therefore s\left(n\right)$ is true for $n=1$

step-2: Assume that the statement $s\left(n\right)$ is true for $n=k$

i.e $4^k-3k-1$ is divisible by 9

then $4^k-3k-1=9m$ ($\therefore m$ is an integer)

$4^k=9m+3k+1\to \left(1\right)$

step-3: We show that the statement $s\left(n\right)$ is true
for $n=k+1$

from (1) we have $4^k-3k-1=9m$

$4^k=9m+3k+1$$4^{k+1}-3(k+1)-1=4^k\cdot 4-3\cdot k-3-1$

$=(9m+3k+1)4-3k-4$

$=4\times 9m+3\times 3k$

$=4\times 9m+9k=9[4m+k]$

$=9n$ $[\therefore N$ is an integer$]$

$\therefore s\left(n\right)$ is true for $n=k+1$

by the principle of mathematical induction $s\left(n\right)$
is true for all $n\in N$