Prove that the equation $3^k = m^2 + n^2 + 1$ has infinitely many solutions in positive integers.

EDIT(ELABORATION)

Note that $$(a^2+b^2)(c^2+d^2)=(ad+bc)^2+(ac-bd)^2 \tag{1}$$ Thus a product of two numbers that are a sum of $2$ squares is als0 a sum of two squares.

CLAIM

For all $t \in \mathbb{N}$, we have that $3^{2^{t}}-1$ is a sum of two squares.

PROOF

It is true when $t=1$ since $$3^{2}-1=2^2+2^2$$ Assume it is true when $t=a$. Note that for $t=a+1$, $$3^{2^{a+1}}-1=\left(3^{2^a} -1 \right) \left(3^{2^a}+1 \right)$$ By the inductive hypothesis, $3^{2^a} -1 $ is a sum of two squares. Also, $3^{2^a}+1$ is a sum of two squares from . Thus, the inductive hypothesis is true when $t=a+1$ from $(1)$. We are done. The result follows, as $k=2^{t}$.

Hint: Prove that if $a^2-1$ is a sum of two square, then $a^{4}-1$ is a sum of two squares.

Thus if $3^{2k}-1$ is the sum of two squares for some $k$, then so is $3^{2^nk}-1$ for any $n$. (You can also prove if $3^{2k}-1$ is the sum of two squares, then so is $3^{k}-1$.)

The hint given by MXYMXY is just the case $k=1$.

The case $k=5$ also has this property, because $$3^{10}-1=(3^5-1)(3^5+1)=8 \cdot 11^2\cdot 61=(11\cdot 22)^2 + 22^2$$ is the sum of two squares. So $3^{5\cdot 2^n}-1$ is always the sum of two squares.