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.
