Results 1 to 2 of 2

Thread: Strong Induction proof

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    310

    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$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by strong induction?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 5th 2009, 07:51 AM
  2. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jul 27th 2009, 06:30 AM
  3. Proof Using Strong Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 23rd 2009, 10:26 AM
  4. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 5th 2008, 12:42 PM
  5. Strong induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2008, 09:48 PM

Search Tags


/mathhelpforum @mathhelpforum