Strong Induction proof

**usagi_killer** · August 24th 2010, 08:48 AM

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$ .

**Isomorphism** · August 24th 2010, 10:01 AM

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?

Thread: Strong Induction proof

LinkBack

Thread Tools

Display

Strong Induction proof

Similar Math Help Forum Discussions

Proof by strong induction?

Proof Using Strong Induction

Proof Using Strong Induction

Strong Induction proof

Strong induction proof

Search Tags