Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer. I am confused as to how to solve this question.
For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds
My induction hypothesis is:
Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a positive integer
So, $2^{2k} -1 = 3m$ 
$2^{2k} = 3m+1$
after this, I'm not quite sure where to go.  Can anyone provide any hints? 

A Combinatorial/Algebraic-Geometric Solution
Consider the operation $*$ on $S:=\{0,1,2,3\}$ defined as follows:


*

*$*$ is commutative with identity $1$,

*$a*0=0=0*a$ for all $a\in S$,

*$2*2=3$, $3*3=2$, and $2*3=1=3*2$.


Now, the elements of $S^n\setminus\{\boldsymbol{0}\}$, where $\boldsymbol{0}:=(0,0,\ldots,0)$ with $n$ zeros, can be partitioned into subsets with $3$ elements of the form $\left\{\mathbf{v},2*\mathbf{v},3*\mathbf{v}\right\}$, where $\mathbf{v} \in S^n\setminus\{\boldsymbol{0}\}$.  Here, we define $a*\mathbf{v}=\left(a*v_1,a*v_2,\cdots,a*v_n\right)$ if $\mathbf{v}=\left(v_1,v_2,\ldots,v_n\right) \in S^n$ and $a\in S$.  The number of partitioning subsets is then $\frac{4^n-1}{3}=\frac{2^{2n}-1}{3}$, which must be an integer.
Remark:  In fact, $S$ can be identified with $\mathbb{F}_4$ and $*$ is simply the usual multiplication on $\mathbb{F}_4$.  The number $\frac{2^{2n}-1}{3}$ is precisely the number of elements of the projective space $\mathbb{PF}_4^{n-1}$.

An Algebraic Solution
Prove that the polynomial $\left(1+x+x^2+x^3\right)^n-1$ is divisible by $1+x+x^2$.  As $1+x+x^2\in\mathbb{Z}[x]$ is monic and $\left(1+x+x^2+x^3\right)^n-1\in\mathbb{Z}[x]$, the quotient $\frac{\left(1+x+x^2+x^3\right)^n-1}{1+x+x^2}$ is a polynomial in $\mathbb{Z}[x]$.  What happens when $x$ is substituted by $1$?

PS: I know that the OP asks for an inductive proof, but there are many interesting ways to overkill this problem.  There is also a geometric solution, using the tiling of an $n$-dimensional hypercube of side length $4$ with tiles consisting of I-shaped $3$-blocks (I-shaped trominos) and one $1$-block (monomino), and this proof is inductive.
