Show that 3 divides $4^n− 1$ where $n$ is a natural number.
We will use induction on $n$. Let the statement $P(n)$ be that $3 \mid $4^n-1$.
We need to prove the base case $P(1)$ and the inductive step $P(n) \implies P(n+1)$.
Base Case
The base case $P(1)$ is $3 \mid 4-1$ which is $3 \mid 3$. This is true.
Induction Step
To prove $P(n) \implies P(n+1)$ we assume the induction hypothesis $P(n)$, and show $P(n+1)$. That is, we assume $3 \mid 4^n -1$ and aim to show $3 \mid 4^{n+1}-1$.
$3 \mid 4^n-1$ means there is some integer $k$ such that
$$ 4^n - 1 = 3k $$
We have
$$ \begin{align} 4^{n+1} -1 & = 4(4^n) - 1 \\ \\ & = 4(3k + 1) - 1 \quad \text{induction hypothesis} \\ \\ &= 3(4k + 1) \end{align} $$
And so we have shown $3 \mid 4^{n+1}-1$.
We have shown by induction that 3 divides $4^n - 1$.