When [tex]n=0[/tex], you have
[tex]4^0=1\equiv3(0)+1=1\mod9[/tex]
Now assume this is true for [tex]n=k[/tex], i.e.
[tex]4^k\equiv3k+1\mod9[/tex]
and under this hypothesis show that it's also true for [tex]n=k+1[/tex]. You have
[tex]4^k\equiv3k+1\mod9[/tex]
[tex]4\equiv4\mod9[/tex]
[tex]\implies 4\times4^k\equiv4(3k+1)\mod9[/tex]
[tex]\implies 4^{k+1}\equiv12k+4\mod9[/tex]
In other words, there exists [tex]M[/tex] such that
[tex]4^{k+1}=9M+12k+4[/tex]
Rewriting, you have
[tex]4^{k+1}=9M+9k+3k+4[/tex]
[tex]4^{k+1}=9(M+k)+3k+3+1[/tex]
[tex]4^{k+1}=9(M+k)+3(k+1)+1[/tex]
and this is equivalent to [tex]3(k+1)+1[/tex] modulo 9, as desired.
