Use induction to prove that $3|(4^n − 1) $ for any integer $n \geq 0$ Use induction to prove that :

$ 3 |(4^n − 1)$ for any integer $n ≥ 0$

Hint: If $k \geq 0$ is an integer then
$4^{(k+1)} = 4\cdot4^k = 3 \cdot4^k + 4^k$.
Honestly have no idea how to even start this one

The case $k = 0$ is self-evident: $3 \mid 0$.
Consider that
$3 \mid 4 - 1, \tag 1$
which is the case $k = 1$;. then since we have
$4(4^k - 1) + 3 = 4^{k + 1} - 4 + 3 = 4^{k + 1} - 1, \tag 2$
if we assume
$3 \mid 4^k - 1, \tag 3$
and recall as in (1) that  
$3 \mid 3, \tag 4$
we see that
$3 \mid 4(4^k - 1) + 3 \tag 5$
directly follows.  Thus, via (2), we obtain
$3 \mid 4^{k + 1} - 1; \tag 6$
So much for an inductive proof of (6).  As simple as this is, an even simpler (non-inductive) proof may be had by observing that
$4^{k + 1} - 1 = (2^2)^{k + 1} - 1 = (2^{k + 1})^2 - 1 = (2^{k + 1} - 1)(2^{k + 1} + 1), \tag 7$
and that $3$ must divide at least one of the three consecutive integers
$2^{k + 1} - 1, 2^{k + 1}, 2^{k + 1} + 1; \tag 8$
since $3 \not \mid 2^{k + 1}, \tag 9$ 
we must have
$3 \mid 2^{k + 1} - 1 \vee 3 \mid 2^{k + 1} + 1, \tag{10}$
and in either case we see that
$3 \mid (2^{k + 1} - 1)(2^{k + 1} + 1), \tag{11}$
from which, by (7), (6) becomes evident as well.
