Results 1 to 2 of 2

Math Help - Strong Induction proof

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    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.
    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 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?
    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: November 5th 2009, 07:51 AM
  2. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 27th 2009, 06:30 AM
  3. Proof Using Strong Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 23rd 2009, 10:26 AM
  4. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 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