Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

rational

  • one year ago

help with induction proof http://prntscr.com/3hnvcf

  • This Question is Closed
  1. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    n = 1 : \(a_1 = 1 \lt 2^1 \) so the given statement is true for n = 1

  2. Ilovecake
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ;)

  3. Ilovecake
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    correct:)

  4. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ty :) im clueless on next step :(

  5. Ilovecake
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh

  6. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    would it be like induction proof from first principle : assume \(a_k = a_{k-1} + a_{k-2} + a_{k-3}\lt 2^k\) and prove \(a_{k+1} \lt 2^k\)

  7. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I would do three cases for the base case. For a1,a2,and a3. You want to assume your statement is true for every integer out to some chosen integer value k and then you want to show it is true for k+1. So let's consider the case of k+1 \[a_{k+1}=a_k+a_{k-1}+a_{k-2}\] we need to look at a_(k-1) and a_k So we know a_k<2^k and a_(k-1)<2^(k-1) by our assumption

  8. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    oops and a_(k-2) so we have also a_(k-2)<2^(k-2)

  9. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh that makes sense 3 base cases ! and yes using second principle we have : \(a_{k} \lt 2^{k} \) \(a_{k-1} \lt 2^{k-1}\) \(a_{k-2} \lt 2^{k-2} \)

  10. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \(a_{k+1}=a_k+a_{k-1}+a_{k-2} \lt 2^k + 2^{k-1} + 2^{k-2}\)

  11. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    yep good so far do you want to try to figure out the trick into showing <2^(k+1)?

  12. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm trying at the moment lol, need to make the right hand side 2^{k+1}

  13. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I used what I wanted to show to help me start out I don't know if that helps you

  14. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    im getting right hand side as : \(2^{k-2}(2^2 + 2 + 1) = 2^{k-2}(7)\)

  15. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    not sure how to conclude... only if that 7 was 8... :o

  16. nipunmalhotra93
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    use 7<8

  17. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it has to be \(\ge 8 \) i think

  18. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I liked factoring out 2^(k+1) instead of 2^(k-2) but you should be able to proceed as you are

  19. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    and nip is right we want <

  20. nipunmalhotra93
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    you have your term <2^(k-2) (7)<2^(k-2) (8)=2^(k+1)

  21. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so far i have this : \(a_{k+1}=a_k+a_{k-1}+a_{k-2} \lt 2^k + 2^{k-1} + 2^{k-2} = 2^{k-2}(7)\)

  22. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ohhh yess !

  23. nipunmalhotra93
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah factoring out 2^(k+1) will do too.

  24. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    thanks a lot that was easier than it looked initally to start wid lol xD

  25. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    or I liked: \[a_{k+1}<2^k+2^{k-1}+2^{k-2}=2^{k+1}(2^{-1}+2^{-2}+2^{-3}) \] \[=2^{k+1}(\frac{1}{2}+\frac{1}{4}+\frac{1}{8})=2^{k+1}(\frac{4+2+1}{8})=2^{k+1}\frac{7}{8}<2^{k+1} \frac{8}{8}=2^{k+1}(1)=2^{k+1}\] Both ways are cute

  26. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    both ways require you to know 7<8 that is interesting

  27. nipunmalhotra93
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah. :D

  28. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    hahah yes this looks easy to read quick :) thank you both :D

  29. myininaya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    hey rational here is another proof you can look at that has the same style we just worked with http://php.scripts.psu.edu/djh300/cmpsc360/ex-strong-induction.htm

  30. nipunmalhotra93
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    you're welcome (Y)

  31. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the proof in that link is very good !! cleared up the mechanics of strong induction thank you very much @myininaya

  32. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy