Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

rational Group Title

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

  • 3 months ago
  • 3 months ago

  • This Question is Closed
  1. rational Group Title
    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

    • 3 months ago
  2. Ilovecake Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    ;)

    • 3 months ago
  3. Ilovecake Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    correct:)

    • 3 months ago
  4. rational Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    ty :) im clueless on next step :(

    • 3 months ago
  5. Ilovecake Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    oh

    • 3 months ago
  6. rational Group Title
    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\)

    • 3 months ago
  7. myininaya Group Title
    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

    • 3 months ago
  8. myininaya Group Title
    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)

    • 3 months ago
  9. rational Group Title
    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} \)

    • 3 months ago
  10. rational Group Title
    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}\)

    • 3 months ago
  11. myininaya Group Title
    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)?

    • 3 months ago
  12. rational Group Title
    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}

    • 3 months ago
  13. myininaya Group Title
    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

    • 3 months ago
  14. rational Group Title
    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)\)

    • 3 months ago
  15. rational Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 3 months ago
  16. nipunmalhotra93 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    use 7<8

    • 3 months ago
  17. rational Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 3 months ago
  18. myininaya Group Title
    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

    • 3 months ago
  19. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    and nip is right we want <

    • 3 months ago
  20. nipunmalhotra93 Group Title
    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)

    • 3 months ago
  21. rational Group Title
    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)\)

    • 3 months ago
  22. rational Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ohhh yess !

    • 3 months ago
  23. nipunmalhotra93 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • 3 months ago
  24. rational Group Title
    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

    • 3 months ago
  25. myininaya Group Title
    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

    • 3 months ago
  26. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

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

    • 3 months ago
  27. nipunmalhotra93 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah. :D

    • 3 months ago
  28. rational Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 3 months ago
  29. myininaya Group Title
    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

    • 3 months ago
  30. nipunmalhotra93 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    you're welcome (Y)

    • 3 months ago
  31. rational Group Title
    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

    • 3 months ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.