How to prove that all odd powers of two add one are multiples of three

Since $2 \equiv -1 \pmod{3}$, therefore $2^{k} \equiv (-1)^k \pmod{3}$. When $k$ is odd this becomes $2^k \equiv -1 \pmod{3}$. Thus $2^k+1 \equiv 0 \pmod{3}$.

A direct alternative to the answer via congruences is to note that for $k$ odd one has the well-known polynomial identity $$ x^{k} + 1 = (x + 1) (x^{k-1} - x^{k-2} + \dots - x + 1), $$ and then substitute $x = 2$.

Another way is by induction:

$$ 2^1+1 = 3 = 3 \cdot 1 $$

Then, if $2^k+1 = 3j, j \in \mathbb{N}$, then

\begin{align} 2^{k+2}+1 & = 4\cdot2^k+1 \\ & = 4(2^k+1)-3 \\ & = 4(3j)-3 \qquad \leftarrow \text{uses induction hypothesis} \\ & = 3(4j-1) \end{align}