Results 1 to 3 of 3

Math Help - Strong induction

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    15

    Strong induction

    Hi,

    I have this proof that I can't find. I have to use strong induction but I don't know how to use it in this case.

    Suppose x is a real number, x \neq 0 and x+1/x is an integer. Prove by strong induction that for all n ≥ 1, x^n +1/x^n is an integer.

    Could someone help me?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TheFangel View Post
    Hi,

    I have this proof that I can't find. I have to use strong induction but I don't know how to use it in this case.

    Suppose x is a real number, x \neq 0 and x+1/x is an integer. Prove by strong induction that for all n ≥ 1, x^n +1/x^n is an integer.

    Could someone help me?
    The base case n=1 is true by assumption, now assume that for some k we have x^j+x^{-j} is an integer for all j \le k.

    Now consider:

    X_{k+1}=\left(x+\frac{1}{x}\right)^{k+1}

    if you examine the expansion you will find that pairs of terms can be grouped together to give integers by the induction hypothesis (with possibly an unpaired middle term which will be an integer on its own) except for the first and last terms which together are:

    u_{k+1}=x^{k+1}+\frac{1}{x^{k+1}}

    Hence as X_{k+1} is an integer as are all the other terms by the induction hypothesis so is [mATH]u_{k+1}[/tex] and so the proof follows by strong induction.

    CB
    Last edited by CaptainBlack; May 26th 2010 at 08:06 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    15
    Quote Originally Posted by CaptainBlack View Post
    The base case n=1 is true by assumption, now assume that for some k we have x^j+x^{-j} is an integer for all j \le k.

    Now consider:

    X_{k+1}=\left(x+\frac{1}{x}\right)^{k+1}

    if you examine the expansion you will find that pairs of terms can be grouped together to give integers by the induction hypothesis (with possibly an unpaired middle term which will be an integer on its own). Hence X_{k+1} is an integer and the proof follows by strong induction.

    CB
    Thanks a lot!
    I'll try that right away!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. STRONG induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 6th 2009, 09:23 PM
  3. Strong Induction help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 7th 2009, 09:48 PM
  4. Strong induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 22nd 2008, 02:00 PM
  5. Strong Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2008, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum