How to prove that all odd powers of two add one are multiples of three 
For example
  \begin{align} 
2^5 + 1 &= 33\\
2^{11} + 1 &= 2049\ \text{(dividing by $3$ gives $683$)}
\end{align}

I know that $2^{61}- 1$ is a prime number, but how do I prove that $2^{61}+1$ is a multiple of three?

Using geometric series
Consider $S_k = 1 + 2\sum_{i=0}^{k-1}4^i$. It follows that $S_k$ is in $\mathbb{N}^{+}$. However,
$$S_k = 1 + 2\cdot\frac{4^k - 1}{4 - 1} = \frac{2^{2k+1}+1}{3}$$
QED
Using recurrence
For $k\in\mathbb{N}$, consider the recurrence $J_{k+1} = 4J_{k} - 1$, with $J_0 = 1$.
Since $J_0 = 1$, it follows that each of $J_k$ is in $\mathbb{N}^{+}$.
Solving the recurrence yields: $J_k = \frac{1}{3}(2^{2k + 1}+ 1)$.

 The characteristic equation $r^2 - 5r + 4 = 0$ follows from $J_{k+2} = 5J_{k+1} - 4J_{k}$. Hence, $J_k = A\lambda_1^k + B\lambda_2^k$, with $\lambda_1 = 4$ and $\lambda_2 = 1$ as solutions to the characteristic equation.  As $J_0 = 1 \implies J_1 = 3$, it follows that $A = \frac{2}{3}$ and $B = \frac{1}{3}$.

QED
