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.

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$.
