1. ## Strong Induction proof

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

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

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

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

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

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

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

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

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

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