Results 1 to 5 of 5

Math Help - Induction Proof

  1. #1
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307

    Induction Proof

    For a real number  x suppose that  x + \frac{1}{x} is an integer. Prove that  x^{n} + \frac{1}{x^{n}} is an integer for all positive integers  n .

    Here is what I did:

    Proof: We use induction on  n . Base case:  x^{1} + \frac{1}{x^{1}} is an integer. Inductive step: Suppose that  x^{k} + \frac{1}{x^{k}} is an integer for some positive  k . Then  \left(x^{k} + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right) =  \frac{x^{k+2}+x^{k}+x^{2-k}+x^{-k}}{x}  = x^{k+1} + x^{k-1} + x^{-k+1} + x^{-k-1}  = \left(x^{k+1} + \frac{1}{x^{k+1}}\right) +  \left(x^{k-1} + \frac{1}{x^{k-1}}\right) (which is an integer by induction hypothesis because an integer multiplied by an integer is an integer). From here, how would I show that  x^{k+1} + \frac{1}{x^{k+1}} is an integer?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    You're nearly there - in fact, you've pretty much proved it!

    You just need to use an alternative kind of induction, called course of values induction. It works along these lines:
    • Say P(n) is the statement you need to prove for all n.
    • Base case: Show P(1).
    • Induction step: Assume P(j) is true for ALL j \leq k; then show P(k+1).
    This assumes more, but it's a perfectly valid way to do induction.

    In your case:

    P(n) :  \left[ x^n + \frac{1}{x^n}\text{ is an integer}  \right]

    The base case has been given already.

    For the inductive step, you rightly considered the expression

    \left( x^k + \frac{1}{x^k} \right) \left( x^1 + \frac{1}{x} \right) \equiv \left( x^{k+1} + \frac{1}{x^{k+1}} \right) + \left( x^{k-1} + \frac{1}{x^{k-1}} \right)

    You know the LHS is an integer, and by course of values induction, \left( x^{k-1} + \frac{1}{x^{k-1}} \right) is an integer.

    (We can assume P(k-1), as well as P(k)!)

    Hence, \left( x^{k+1} + \frac{1}{x^{k+1}} \right) is an integer, as on the RHS, integer + integer = integer.

    QED!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    aaahhh, that was what I was thinking. I needed to use strong induction right?

    Thanks a lot.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    Yeah, it's also known as strong induction or 'complete induction', apparently.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tukeywilliams View Post
    For a real number  x suppose that  x + \frac{1}{x} is an integer. Prove that  x^{n} + \frac{1}{x^{n}} is an integer for all positive integers  n .

    Here is what I did:

    Proof: We use induction on  n . Base case:  x^{1} + \frac{1}{x^{1}} is an integer. Inductive step: Suppose that  x^{k} + \frac{1}{x^{k}} is an integer for some positive  k . Then  \left(x^{k} + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right) =  \frac{x^{k+2}+x^{k}+x^{2-k}+x^{-k}}{x}  = x^{k+1} + x^{k-1} + x^{-k+1} + x^{-k-1}  = \left(x^{k+1} + \frac{1}{x^{k+1}}\right) +  \left(x^{k-1} + \frac{1}{x^{k-1}}\right) (which is an integer by induction hypothesis because an integer multiplied by an integer is an integer). From here, how would I show that  x^{k+1} + \frac{1}{x^{k+1}} is an integer?

    Thanks
    The problem of the week!

    Yes, the trick here is the ordinary induction does not work. You need to use strong induction.
    ----
    Another way to do this, which is longer, but much more fun.
    Isto consider the Binomial expansion of:
    \left( x + \frac{1}{x} \right)^n

    This is more fun because then you need to consider even and odd n and you take advantage of all 1,2,3,...,n cases. Unlike here where you just use n-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum