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: Note that
$$\sum_{k=0}^{n-1} 4^k={4^n-1\over4-1}$$
is an integer.
A: Hint: If $2^{2k} - 1$ is divisible by $3$, then write
\begin{align*}
2^{2(k + 1)} - 1 &= 2^{2k + 2} - 1 \\
&= 4 \cdot 2^{2k} - 1 \\
&= 4 \cdot \Big(2^{2k} - 1\Big) + 3
\end{align*}
Do you see how to finish it up?

This technique is motivated by attempting to shoehorn in the term $2^{2k} - 1$, since that's the only piece we really know anything meaningful about.
A: If we rewrite $2^{2k}-1$ in binary, we get the number 
$$2^{2k}-1=\underset{\text{$2k$-times}}{\underbrace{111111\dots11}}$$
consisting of $2k$ ones. (I.e., there are $k$ pairs of them.)
If this is not clear immediately, just notice that by adding one to the above number we get
$$2^{2k}=1\underset{\text{$2k$-times}}{\underbrace{000000\dots00}}.$$
Now we can simply notice that this number can be obtained as the sum (written in binary)
$$
\begin{align*}
110000\dots00&+\\
  1100\dots00&+\\
        \dots&+\\
           11&=\\
111111\dots11&
\end{align*}
$$
where each summand is multiple of $3=(11)_2$.
A: 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.
A: $$2^{2k} - 1
= (2^k)^2 - 1 = (2^k - 1) (2^k +1)
$$
For any even number $2^k$, after divided by 3, there are two possible remainders, 1 or 2.
If the remainder of $2^k$ divided by 3 is 1, then $2^k - 1$ is divisible by 3.
If the remainder of $2^k$ divided by 3 is 2, then $2^k + 1$ is divisible by 3.
So no matter what remaider is, $(2^k - 1)(2^k +1)$, is divisible by 3, so as $2^{2k}$. 
A: Here are a couple graphical demonstrations of induction for this problem, based on tiling square regions with L-shaped trominoes:
http://www.mathdemos.org/mathdemos/tromino/tromino.html
https://www.math.hmc.edu/funfacts/ffiles/20002.4.shtml
