Question

Use mathematical induction to show that 4^n ≡ 3n+1 (mod 9) for all n equal to or greater than 0

Answer 1

When $n=0$, you have

$4^0=1\equiv3(0)+1=1\mod9$

Now assume this is true for $n=k$, i.e.

$4^k\equiv3k+1\mod9$

and under this hypothesis show that it's also true for $n=k+1$. You have

$4^k\equiv3k+1\mod9$
$4\equiv4\mod9$
$\implies 4\times4^k\equiv4(3k+1)\mod9$
$\implies 4^{k+1}\equiv12k+4\mod9$

In other words, there exists $M$ such that

$4^{k+1}=9M+12k+4$

Rewriting, you have

$4^{k+1}=9M+9k+3k+4$
$4^{k+1}=9(M+k)+3k+3+1$
$4^{k+1}=9(M+k)+3(k+1)+1$

and this is equivalent to $3(k+1)+1$ modulo 9, as desired.