Results 1 to 10 of 10

Math Help - Mathematical Induction

  1. #1
    Junior Member
    Joined
    Jul 2009
    Posts
    40

    Question Mathematical Induction

    Let p greater than or equal to 3 be an integer.Alpha and beta are the roots of x^2-(p+1)x+1=0.Using mathematical induction ,prove that alpha^n+beta^n
    1)is an integer
    2)is not divisible by p
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jul 2009
    Posts
    40

    Please check my solution

    I've solved the first part of the question in the following way(with the help of second hypothesis):

    Given :x^2-(p+1)x+1=0 and alpha and beta are the roots .
    so, alpha+beta = p+1 ..............(1) and alpha+beta is greater than or equal to 4.............(2){since it is given that p>=3}
    alpha x beta =1 ................(3)

    STEP1 -- To prove that P(1) is an integer.
    alpha^1+beta^1 =alpha+beta -------> is an integer. [from (1)]

    To prove that P(2) is an integer.
    P(2)=alpha^2+beta^2=(alpha+beta)^2- 2alpha .beta
    {(alpha+beta)^2 is >=16 [from 2] , 2alpha .beta =2 [from 3]
    so, the value of alpha^2+beta^2=(alpha+beta)^2- 2alpha .beta becomes >=14 and hence it is an integer.}

    STEP 2 INDUCTION ASSUMPTION
    --------------------------------
    Let P(k) be an integer.
    so, alpha^k +beta^k be an integer.
    Let P(k-1) be an integer.
    so,alpha^(k-1) +beta^(k-1) be an integer.

    Step3 -- To prove that P(k+1) is an integer.
    P(k)=alpha^(k+1) +beta^(k+1)
    =(alpha^k +beta^k )(alpha+beta) - alpha^k.beta-beta^k.alpha
    =(alpha^k +beta^k )(alpha+beta) - alpha .beta{alpha^(k-1)+beta^(k-1)}

    USING-
    alpha+beta is greater than or equal to 4.............(2)
    alpha x beta =1 ................(3)
    (alpha^k +beta^k )(alpha+beta) >=4 [from above 2 relations]
    and
    alpha^(k-1)+beta^(k-1)

    From induction assumption
    , alpha^k +beta^k is an integer and alpha^(k-1) +beta^(k-1) is also an integer.

    Hence it has been proved that (alpha^k +beta^k )(alpha+beta) - alpha .beta{alpha^(k-1)+beta^(k-1)} is an integer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2009
    Posts
    40
    I've solved the second part by second hypothesis of induction.

    alpha + beta= p+1
    this implies that alpha+beta is not divisible by p...........(1)

    and alpha x beta=1 .............(2)


    STEP1 -- To prove that P(1) is not divisible by p.
    alpha^1+beta^1=alpha+beta is not divisible by p.[from (1)]

    To prove that P(2) is not divisible by p.
    alpha^2+beta^2=(alpha+beta)^2 - 2 .alpha beta is not divisible by p

    STEP2(INDUCTION ASSUMPTION) -- Let P(k) and P(k-1) be true.
    so, alpha^k+beta^k is not divisible by p. ............(3)
    and alpha^(k-1)+beta^(k-1) is not divisible by p..............(4)

    STEP3 -- To prove that P(k+1) is not divisible by p.
    P(k+1)=alpha^(k+1)+beta^(k+1)
    =(alpha^k+beta^k)(alpha+beta) - alpha^kbeta -beta.alpha^k
    =(alpha^k+beta^k)(alpha+beta) - alpha.beta{alpha^(k-1)+beta^(k-1)}


    from(INDUCTION ASSUMPTION)
    alpha^k+beta^k is not divisible by p............(3)
    and alpha^(k-1)+beta^(k-1) is not divisible by p..............(4)

    I'm stuck at this point.
    then, how to prove (alpha^k+beta^k)(alpha+beta) - alpha.beta{alpha^(k-1)+beta^(k-1)} is not divisible by p.

    I've solved this question many times but haven't proved it perfectly.
    Last edited by mr fantastic; July 4th 2009 at 11:30 PM. Reason: Merged posts
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Quote Originally Posted by matsci0000 View Post
    Let p greater than or equal to 3 be an integer.Alpha and beta are the roots of x^2-(p+1)x+1=0.Using mathematical induction ,prove that alpha^n+beta^n
    1)is an integer
    2)is not divisible by p


    We have

     \alpha+ \beta = p+1
    and
     \alpha\beta = 1


     \alpha^{k+2} + \beta^{k+2} = (\alpha + \beta)(\alpha^{k+1} + \beta^{k+1}) - \alpha \beta(\alpha^{k} + \beta^{k})

     \alpha^{k+2} + \beta^{k+2} = (p+1)(\alpha^{k+1} + \beta^{k+1}) - (\alpha^{k} + \beta^{k})

    S_1 and  S_2 are true , now , assume  S_{k} and  S_{k+1} ~ are also true .

    Obviously , refering to the identity ,  S_{k+2}~~ are true


    For part 2 , assume  S_{k-1} , S_{k} , S_{k+1} are true.

     \alpha^{k+2} + \beta^{k+2} = (p+1)(\alpha^{k+1} + \beta^{k+1}) - (\alpha^{k} + \beta^{k})

    To prove  S_{k+2}~ is also true , we have to prove  A_{k+1} - A_{k}=/= 0mod(p) Where A_k = \alpha^{k} + \beta^{k}


     A_{k+1} - A_{k}=  \alpha^{k+1} + \beta^{k+1} - \alpha^{k} - \beta^{k}

     = \alpha^{k}(\alpha-1) + \beta^{k}(\beta - 1)
     = \alpha^{k}(p-\beta) + \beta^{k}(p-\alpha)
     = p(\alpha^{k} + \beta^{k}) - (\alpha \beta)( \alpha^{k-1} + \beta^{k-1})
     = p(integer) + (\alpha^{k-1} + \beta^{k-1}) =/= 0mod(p)
    Last edited by simplependulum; July 4th 2009 at 11:53 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    First part of your solution

    Hello matsci0000

    Thanks for showing us your working. This part is pretty well OK, except for where I've commented.
    Quote Originally Posted by matsci0000 View Post
    I've solved the first part of the question in the following way(with the help of second hypothesis):

    Given :x^2-(p+1)x+1=0 and alpha and beta are the roots .
    so, alpha+beta = p+1 ..............(1)
    Correct. But you don't need this bit:
    and alpha+beta is greater than or equal to 4.............(2){since it is given that p>=3}


    alpha x beta =1 ................(3)
    Correct. Notice that this now shows that \alpha+\beta and \alpha\beta are integers.

    STEP1 -- To prove that P(1) is an integer.
    alpha^1+beta^1 =alpha+beta -------> is an integer. [from (1)]

    To prove that P(2) is an integer.
    P(2)=alpha^2+beta^2=(alpha+beta)^2- 2alpha .beta
    Correct, and this is all you need, in order to show that \alpha^2+\beta^2 is an integer. So you don't need this bit:
    {(alpha+beta)^2 is >=16 [from 2] , 2alpha .beta =2 [from 3]
    so, the value of alpha^2+beta^2=(alpha+beta)^2- 2alpha .beta becomes >=14 and hence it is an integer.}
    Now for the next part:
    STEP 2 INDUCTION ASSUMPTION
    --------------------------------
    Let P(k) be an integer.
    so, alpha^k +beta^k be an integer.
    Let P(k-1) be an integer.
    so,alpha^(k-1) +beta^(k-1) be an integer.

    Step3 -- To prove that P(k+1) is an integer.
    P(k)=alpha^(k+1) +beta^(k+1)
    You mean P(k+1) here, of course.
    =(alpha^k +beta^k )(alpha+beta) - alpha^k.beta-beta^k.alpha
    =(alpha^k +beta^k )(alpha+beta) - alpha .beta{alpha^(k-1)+beta^(k-1)}
    This is fine. In other words

    P(k+1) = P(k)(\alpha+\beta)-\alpha\beta P(k-1)

    So this, together with your assumptions that P(k) and P(k-1) are integers and the fact that \alpha + \beta and \alpha\beta are both integers is all you need to show that P(k+1) is an integer.

    Since you've already established that P(1) and P(2) are integers, this completes the proof.

    So you don't need this bit:

    USING-
    alpha+beta is greater than or equal to 4.............(2)
    alpha x beta =1 ................(3)
    (alpha^k +beta^k )(alpha+beta) >=4 [from above 2 relations]
    and
    alpha^(k-1)+beta^(k-1)


    I haven't time now to look at your proof of part 2. If no-one else has commented on it, I'll do so later.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,832
    Thanks
    1602
    Part 2:

    We know the following:

    \alpha + \beta = p + 1

    \alpha\beta = 1

    P(k + 1) = \alpha^{k + 1} + b^{k + 1} = (\alpha^k + \beta^k)(\alpha + \beta) - \alpha\beta(\alpha^{k - 1} + \beta^{k - 1}).


    So P(k + 1) = (\alpha^k + \beta^k)(p + 1) - 1(\alpha^{k - 1} + \beta^{k - 1})

     = (p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})


    Try dividing P(k + 1) by p.


    \frac{P(k + 1)}{p} = \frac{(p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})}{p}

     = \frac{(p + 1)(\alpha^k + \beta^k)}{p} - \frac{\alpha^{k - 1} + \beta^{k - 1}}{p}.


    Clearly p + 1 can not be divided by p exactly, and you have already established that \alpha^k + \beta^k and \alpha^{k - 1} + \beta^{k - 1} are not divisible by p, so P(k + 1) can not be divided by p.

    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Induction proof - part 2

    Hello everyone -

    I don't think any of the proofs so far are really complete, although simplependulum has all but done it - without adequately testing the initial hypotheses. (Where, for instance, is the requirement that p \ge 3?)

    I'm afraid ProveIt's last line doesn't work. Just because \frac{A}{p} is not an integer and \frac{B}{p} is not an integer doesn't necessarily mean that \frac{A-B}{p} is not an integer.

    May I suggest the following.

    Using the notation P(k) = \alpha^k +\beta^k, and the proofs so far offered, we know that

    P(k+1) = (p+1)P(k) - P(k-1)

    = pP(k) + P(k) - P(k-1)

    \Rightarrow P(k+1) \equiv P(k)-P(k-1) \mod p. Call this equation (1)


    If we now replace k by (k-1) in this equation we get:

    P(k) \equiv P(k-1) - P(k-2) \mod p

    \Rightarrow P(k+1) \equiv P(k-1) - P(k-2) - P(k-1) \mod p

    \Rightarrow P(k+1) \equiv -P(k-2) \mod p

    Therefore if P(k-2) is not a multiple of p, then P(k+1) isn't either.


    So, provided P(1), P(2) and P(3) are not multiples of p, we have sufficient to show that P(k) is not a multiple of p for all integers k \ge 1.


    P(1) = \alpha + \beta = p+1 \Rightarrow P(1) is not a multiple of p

    P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)

    \Rightarrow P(2) \equiv (p-1) \mod p

    \Rightarrow P(2) \ne 0 \mod p, for p \ge 2

    P(3) \equiv P(2) - P(1) \mod p (using equation (1) with k = 2)

    \Rightarrow P(3) \equiv (p-1) - 1 \mod p

    \Rightarrow P(3) \equiv (p-2) \mod p

    \Rightarrow P(3) \ne 0 \mod p, for p\ge 3


    And that completes the proof, I think.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jul 2009
    Posts
    40

    Thumbs down Argument

    Solution given by prove it(MHF contributor):
    We know the following:

    \alpha + \beta = p + 1

    \alpha\beta = 1

    P(k + 1) = \alpha^{k + 1} + b^{k + 1} = (\alpha^k + \beta^k)(\alpha + \beta) - \alpha\beta(\alpha^{k - 1} + \beta^{k - 1}).


    So P(k + 1) = (\alpha^k + \beta^k)(p + 1) - 1(\alpha^{k - 1} + \beta^{k - 1})

     = (p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})


    Try dividing P(k + 1) by p.


    \frac{P(k + 1)}{p} = \frac{(p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})}{p}

     = \frac{(p + 1)(\alpha^k + \beta^k)}{p} - \frac{\alpha^{k - 1} + \beta^{k - 1}}{p}.


    Clearly p + 1 can not be divided by p exactly, and you have already established that \alpha^k + \beta^k and \alpha^{k - 1} + \beta^{k - 1} are not divisible by p, so P(k + 1) can not be divided by p.
    The problem of the question lies HERE.
    It is true that \alpha^k + \beta^k and \alpha^{k - 1} + \beta^{k - 1} are not divisible by p
    ------------------------------------------------------------------------------------------------

    But you can not say that the difference between \alpha^k + \beta^k and \alpha^{k - 1} + \beta^{k - 1}
    is not divisible by p.

    The above argument given by me can be more clear from the following example-
    7 is not divisible by 3 and 4 is also not divisible by 3
    But their difference which is equal to 3 is divisible by 3.
    Last edited by matsci0000; July 7th 2009 at 06:54 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jul 2009
    Posts
    40
    Quote Originally Posted by Grandad View Post
    Hello everyone -

    I don't think any of the proofs so far are really complete, although simplependulum has all but done it - without adequately testing the initial hypotheses. (Where, for instance, is the requirement that p \ge 3?)

    I'm afraid ProveIt's last line doesn't work. Just because \frac{A}{p} is not an integer and \frac{B}{p} is not an integer doesn't necessarily mean that \frac{A-B}{p} is not an integer.

    May I suggest the following.

    Using the notation P(k) = \alpha^k +\beta^k, and the proofs so far offered, we know that

    P(k+1) = (p+1)P(k) - P(k-1)

    = pP(k) + P(k) - P(k-1)

    \Rightarrow P(k+1) \equiv P(k)-P(k-1) \mod p. Call this equation (1)


    If we now replace k by (k-1) in this equation we get:

    P(k) \equiv P(k-1) - P(k-2) \mod p

    \Rightarrow P(k+1) \equiv P(k-1) - P(k-2) - P(k-1) \mod p

    \Rightarrow P(k+1) \equiv -P(k-2) \mod p

    Therefore if P(k-2) is not a multiple of p, then P(k+1) isn't either.


    So, provided P(1), P(2) and P(3) are not multiples of p, we have sufficient to show that P(k) is not a multiple of p for all integers k \ge 1.


    P(1) = \alpha + \beta = p+1 \Rightarrow P(1) is not a multiple of p

    P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)

    \Rightarrow P(2) \equiv (p-1) \mod p

    \Rightarrow P(2) \ne 0 \mod p, for p \ge 2

    P(3) \equiv P(2) - P(1) \mod p (using equation (1) with k = 2)

    \Rightarrow P(3) \equiv (p-1) - 1 \mod p

    \Rightarrow P(3) \equiv (p-2) \mod p

    \Rightarrow P(3) \ne 0 \mod p, for p\ge 3


    And that completes the proof, I think.

    Grandad
    Thanks Grandad for the proof but I do not know anything about modulus and its operations.Is there any other alternate solution for this?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Modular arithmetic

    Hello matsci0000
    Quote Originally Posted by matsci0000 View Post
    Thanks Grandad for the proof but I do not know anything about modulus and its operations.Is there any other alternate solution for this?
    Yes. The modular arithmetic notation I used is a convenient way of discussing remainders when one integer is divided by another. But instead of using the mod notation, we can write the proof out as follows (it just looks a bit more complicated, that's all).

    In the proof that follows, A, B, ...
    are integers.

    P(k+1) = (p+1)P(k) - P(k-1)

    = pP(k) + P(k) - P(k-1)

    \Rightarrow P(k+1) =Ap+ P(k)-P(k-1)
    . Call this equation (1)


    If we now replace k by (k-1) in this equation we get:

    P(k) = Bp+P(k-1) - P(k-2)

    \Rightarrow P(k+1) =(A+B)p +P(k-1) - P(k-2) - P(k-1)

    \Rightarrow P(k+1) =(A+B)p -P(k-2)

    Therefore if P(k-2) is not a multiple of p, then P(k+1) isn't either.


    So, provided P(1), P(2) and P(3) are not multiples of p, we have sufficient to show that P(k) is not a multiple of p for all integers k \ge 1.


    P(1) = \alpha + \beta = p+1 \Rightarrow P(1) leaves a remainder 1
    when divided by p.

    P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)

    \Rightarrow P(2) =Cp+ (p-1)

    \Rightarrow P(2)
    leaves a remainder (p-1)> 0, for p \ge 2

    P(3) = Dp+ P(2) - P(1) (using equation (1) with k = 2)

    \Rightarrow P(3) = (C+D)p + (p-1) - (p+1)

    \Rightarrow P(3) = (C+D-1)p + (p - 2)

    \Rightarrow P(3) leaves a remainder (p-2) > 0, for p \ge 3, when divided by p.


    That completes the proof.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 04:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 06:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 06:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 09:35 AM

Search Tags


/mathhelpforum @mathhelpforum