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}

One of your examples is that $2^{11} + 1$ is divisible by $3$. We investigate as follows:

Let us consider instead raising $2$ to an even power and subtracting $1$. And then let us factor.

Example: $2^{10} - 1 = (2^5 - 1)(2^5 + 1)$.

Among any three consecutive integers, exactly one of them must be divisible by $3$.

Clearly $2^5$ is not divisible by $3$, so either its predecessor or successor is divisible by $3$.

That is, either $2^5 - 1$ or $2^5 + 1$ is divisible by $3$, whence their product is, as well.

Okay: Their product is $2^{10} - 1$, which we have now established is divisible by $3$.

This number is still divisible by $3$ after being doubled, and still divisible by $3$ when we add $3$ to it.

So: We have that $2(2^{10} - 1) + 3 = 2^{11} - 2 + 3 = 2^{11} + 1$ is divisible by $3$ as desired.

A similar bit of reasoning around $2^{2k} - 1$ yields the assertion at hand. "QED"