Use the PMI to prove the following $4^{k}-1$ is divisible by 3. $4^{n}-1$ is divisible by $3.$


(i) Basis Step: $P(1)$is true because $4^1 -1=3 $ and $3\mid3$.

(ii) Suppose $P(k)$ is true for induction hypothesis $3\mid4^{k}-1$. 

Show $(k+1)$ is true $3\mid4^{k+1}$ 

Now here is where things gets tricky.

$\Rightarrow 4^{k+1} -1 = \left(4^{k}*4 \right)-1 =$ 

I cannot seem to figure out how one factors this any further. I just cannot seem to make it divisible by 3. Could someone show me how to do this?
Inductive assumption: $3 \mid (4^k-1)$, and therefore $(4^k-1) = 3m$ for some $m$.

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

so $4^{k+1}-1= 4(4^k-1)+3 = 12m+3$ which is divisible by $3$, completing the induction.
Rewrite statement (*) as $(3+1)^n =3k+1.$ When $n=1$ let $k=1.$ 

Assume $(3+1)^n =3k+1 $. $(3+1)(3k+1)=3(3k+1)+3k+1=3(3k+1+k)+1 .$