Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Several Induction questions

  1. Mar 13, 2010 #1
    2 Induction Questions

    1. The problem statement, all variables and given/known data
    I have quite a few questions and so i just made it an image. Also attached.
    http://img411.imageshack.us/img411/1002/inductionforlife.jpg" [Broken]
    Only need help with questions 2 and 5 now

    Oh and so far my lecturer has taught well-ordering, strong induction and simple induction. But I could only follow simple induction... the other two I'm quite clueless about >< Though tell me which method is best for each question.

    2. Relevant equations
    Refer to image

    3. The attempt at a solutions
    Question 2
    I have no clue to how to start it..
    All i have done is
    24 = 7 + 7 + 5 + 5
    25 = 5 + 5 + 5 + 5 + 5
    26 = 7 + 7 + 7 + 5
    27 = 7 + 5 + 5 + 5 + 5
    28 = 7 + 7 + 7 + 7
    29 = 7 + 7 + 5 + 5 + 5
    no idea what to do now

    [STRIKE]Question 3
    I'm not sure if my method is correct but I've proved that when x = 0 and n = 1, x = 1 n = 2 are true. But I get stuck whilst proving n = k + 1

    Let Sn be (1 + x)n >= 1 + nx
    For n = 1 and x = 0, S1 =
    LHS = (1+0)1 = 1
    RHS = 1 + (1)(0) = 1
    Therfore LHS >= RHS Hence n = 1 is true.

    Assume n = k is true
    Sk --> (1 + x)k >= 1 + kx

    For n = k + 1, Sk+1 =

    I know that I need to get to
    (1 + x)k+1 >= 1 + (k+1)x

    (1 + x)k >= 1 + kx
    (1 + x)k(1 + x)1 >= (1 + kx)(1 + x)1 (multiplied both sides by (x + 1)
    (1 + x)k+1 >= 1 + x + kx + kx2

    I can see that on the RHS there is 1 + x + kx I'm not sure what to do with it... hints/help?

    Question 4 (Just needs checking)

    Let Sn be ƒ1 + ƒ2 + ... + ƒn = ƒn+2 -1
    For n = 1, S1
    LHS = ƒ1 = 1
    RHS = ƒ1+2 - 1 = 2 - 1 = 1
    LHS = RHS
    Therefore n = 1 is true

    Assume true for n = k
    Sk --> ƒ1 + ƒ2 + ... + ƒk = ƒk+2 -1

    For n = k + 1, Sk+1 =
    RHS = ƒk+3 - 1
    LHS = ƒ1 + ƒ2 + ... + ƒk + ƒk+1
    = ƒk+2 -1 + ƒk+1
    = ƒk+2 + ƒk+1 - 1
    = ƒk+3 - 1 (should I write any reason here? if yes..what should i write?)
    = RHS
    Hence n = k + 1 is true
    By mathematical induction Sn is true for all positive integers n.
    [/STRIKE]
    Question 5
    Show that n/t - 1/(q+1) is positive and numerator is less than n
    where t = nq + r with 0 < r < n

    (get common denominator then expand and simplify)
    n/t - 1/(q+1)
    = n(q + 1)/[t(q+1)] - t/[t(q+1)]
    = [n(q+1) - t] / [t(q+1)]
    = [nq - t + n] / [t(q+1)]

    t = nq + r
    nq - t = -r

    hence n/t - 1/(q+1)
    = [n-r] / [t(q+1)]

    from 0 < r < n
    n > r therefore n - r > 0 (proved that numerator is positive)
    and since r > 0 then n - r < n (proved that numerator is < n)

    I'm not sure where to go from here

    Please someone help me however you can..
    Thank you in advance!!
     

    Attached Files:

    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Mar 14, 2010 #2
    Bump (updated)
     
  4. Mar 14, 2010 #3

    Mark44

    Staff: Mentor

    It's better to post one question at a time rather than post a whole slew of them.
     
  5. Mar 14, 2010 #4
    Its only two questions now ><
    and they dont have to answer them all...just whichever ones they can ><
     
    Last edited: Mar 14, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook