Prove $4^n-1$ is divisible by $3$, for all $n\in\Bbb N$? Prove $4^n-1$ is divisible by $3$, for all $n\in\Bbb N$?
I started by assuming there exists some $k\in\Bbb N$ s.t. $4^n-1=3k\iff \dfrac{4^n}3-\dfrac 13=k$, so for $k$ to be a natural number, $4^n\equiv 1\mod 3$ must be true, but this tells us no new information, and I don't know how to follow from there. Any help would be appreciated.
 A: Note that
$$4^n-1\equiv(1)^n-1\equiv 0 \mod 3$$
A: With only middle school tools:
$$4^n-1=4^n-1^n=(\underbrace{4-1}_{\textstyle 3})(4^{n-1}+4^{n-2}+\dots +4+1).$$
A: The simples way is using modular arithmetic, under which
$$4^n-1\equiv 1^n-1\equiv 1-1\equiv 0\mod 3$$

Another way is to write
$$4^n = (3+1)^n$$
and use the binomial formula to get
$$(3+1)^n = 3^n +{n\choose 1} 3^{n-1} + \cdots + {n\choose n-1} 3^1 + 1\\=3\left(3^{n-1} +{n\choose 1} 3^{n-2} + \cdots + {n\choose n-1} 3^0 \right) + 1$$

A third way would be to use induction. The step $n=1$ is simple, as $4^n-1=4-1=3$ is clearly divisible by $3$.
The induction step uses the fac that since $4^n-1$ is divisible by $3$, there exists some $k$ such that $4^n-1=3k$, therefore $4^n=3k+1$ and
$$4^{n+1} - 1=4\cdot 4^n - 1 = 4\cdot (3\cdot k + 1) - 1 = 12 k + 3 = 3(4k+1)$$ 
which is divisible by $3$.
A: Or
$$ 4^n-1 = (4-1)(4^{n-1}+4^{n-2}+...+4^2+4+1)$$
or 
$$4^n-1 = (3+1)^n-1 = \underbrace{{n\choose 0}3^n+ {n\choose 1}3^{n-1}+...+{n\choose n-1}3}_{3k}+ 1-1$$
A: $$4=3+1\implies 4^n \equiv 1^n \pmod 3$$
A: $$4^n-1=(2^n)^2-1=(2^n+1)(2^n-1)$$
One of $2^n+1,2^n-1$ must be divisible by $3$, because the contrary implies that $2^n$ is divisible by $3$.
A: Alternatively, with induction: assuming $4^n-1\equiv 0 \mod 3$ is true, we will show for $n+1$:
$$4^{n+1}-1=4\cdot (4^n-1)+4-1\equiv 0 \mod 3.$$
