For all $n$, there are integers $x$, $y$, $z$ such that $x^2 + y^2 = z^n$ Prove that $\forall n \in \mathbb{N},$ there exist integers $x,y,z$ such that $x^2+y^2=z^n$. 
I know that this is an induction proof, and I am assuming this needs to be broken up into cases where n is even and where n is odd.
But how do I even start doing this? 
 A: Let's assume you mean "nonzero integers", otherwise the claim is obviously true (since $x=y=z=0$ satisfies the equation).
I would advise you to split the statement into two statements:
Statement 1:
If $n$ is even, then there exist integers $x,y,z$ such that $x^2+y^2=z^n$. 
Statement 2:
If $n$ is odd, then there exist integers $x,y,z$ such that $x^2+y^2=z^n$. 

Proof for statement $1$:
The statement is equivalent to

For all $k\in\mathbb N$, there exist integers $x,y,z$ such that $x^2+y^2=z^{2k}$. 

which can be proven by induction.
For $k=1$, the statement should be easy to prove.
For $k\to k+1$, look at what happens to your equation when you multiply it by $z^2$.

With statement $2$, again, you can rewrite it to

For all $k\in\mathbb N$, there exist integers $x,y,z$ such that $x^2+y^2=z^{2k - 1}$. 

which is even simpler to prove for $k=1$, while the $k\to k+1$ step is practically identical to the previous statement.
A: It suffices to give explicit solutions. I'll give them using $z=5$.
$n=1$: $\quad 5=1^2+2^2$
$n \to n+1:$  $\quad 5^n = x^2+y^2 \implies 5^{n+1} = (x-2y)^2+(2x+y)^2$
This follows from the Brahmagupta–Fibonacci identity.
This identity has a nice interpretation with complex numbers, which in this case is:
$$
5 = |1+2i|^2, \quad 5^n=|x+yi|^2 \\\implies  5^{n+1} =|x+yi|^2 |1+2i|^2 = |(x+yi)(1+2i)|^2 = |(x-2y)+(2x+y)i|^2
$$
