Prove by Induction on n that $\exists x,y,z \in Z$ s.t. $x\ge 2, y\ge 2, z\ge 2$ satisfies $x^2+y^2=z^{2n+1}$

Question

Prove by Induction on n that $\exists x,y,z \in Z$ s.t. $x\ge 2, y\ge 2, z\ge 2$ satisfies $x^2+y^2=z^{2n+1}$

I'm a lot more comfortable with proving induction with $\forall$ I haven't really seen one of this format yet where there's an $\exists$. Since this is obviously not true for all $x,y,z\in Z$ it's harder for me to figure out how to solve it.

Answer 1

Well, if $x^2 + y^2 = z^{2n+1}$ then

$x^2z^2 + y^2z^2 = z^{2n+1}z^2$

Answer 2

Remark. This problem is much easier to prove without induction. But, well, since it is required, I will oblige. However, if you look carefully, this is exactly the same as what I wrote in my comment under the OP's question.

For each integer $n\geq 0$, we want to find $(x_n,y_n,z_n)\in\mathbb{Z}^3$ such that $$x_n^2+y_n^2=z_n^{2n+1}\,.$$ For the basis of our induction, start with $(x_0,y_0,z_0):=(a,b,a^2+b^2)$ for an arbitrary pair $(a,b)\in\mathbb{Z}^2$. For an integer $n\geq 1$, suppose you have $\left(x_{n-1},y_{n-1},z_{n-1}\right)$. Define $$(x_n,y_n,z_n):=\left(x_{n-1}z_{n-1},y_{n-1}z_{n-1},z_{n-1}\right)\,.$$ Prove that this triple $(x_n,y_n,z_n)$ satisfies $x_n^2+y_n^2=z_n^{2n+1}$.

In fact, the same argument shows that, for each $k\in\mathbb{Z}_{>0}$, there are infinitely many integers $(x,y,z)\in\mathbb{Z}^3$ or $(x,y,z)\in\mathbb{Z}_{>0}^3$ such that $$x^2+y^2=z^k\,.$$ The case where $k$ is odd has been dealt with. For an even $k$, we start with a Pythagorean triple $(a,b,c)\in\mathbb{Z}^3$ (or $(a,b,c)\in\mathbb{Z}_{>0}^3$), i.e., $a^2+b^2=c^2$. Then, $$(x,y,z)=\left(ac^{\frac{k}{2}-1},bc^{\frac{k}{2}-1},c\right)$$ is a solution to $x^2+y^2=z^k$. You can, of course, write this proof inductively as well.

Answer 3

Hint: The Brahmagupta–Fibonacci identity implies that if $z_1$ and $z_2$ are sums of squares, then so is their product $z_1 z_2$.