1. ## Strong Induction proof

Using strong mathematical induction, for each $n \in \mathbb{N}$ prove that there exist positive integers $x, y, z$ satisfying $x^2 + y^2 = z^n$.

2. Let $P(k):$ There exists $(x_0,y_0,z_0)$ such that $x_0^2 + y_0^2 = z_0^k$, where $k \in \mathbb{N}$.

First we will show that P(1) and P(2) are true.

$P(1):$ There exists $(x_0,y_0,z_0)$ such that $x_0^2 + y_0^2 = z_0$.
$(x,y,z) = (1,1,2)$ satisfies the equation $x^2 + y^2 = z$ and hence P(1) is true.

$P(2):$ There exists $(x_0,y_0,z_0)$ such that $x^2 + y^2 = z^2$.
$(x,y,z) = (3,4,5)$ satisfies the equation $x_2 + y^2 = z^2$ and hence P(2) is true.

Strong Induction Hypothesis: The proposition $P(k)$ is true for all $k < n$

We will show that $P(n)$ is true.

By strong induction hypothesis, $P(n-2)$ is true. This means there exists $(x_0,y_0,z_0)$ such that $x_0^2 + y_0^2 = z_0^{n-2}$. Multiply the equation by $z_0^2$ to get $(z_0x_0)^2 + (z_0y_0)^2 = z_0^{n}$. So the integer triple $(z_0x_0,z_0y_0,z_0)$ satisfies $x^2 + y^2 = z^{n}$
Hence $P(n)$ is true.

Observe that I have proved $P(1)$ and $P(2)$ initially.

Question: Is it sufficient to prove P(1) alone?