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

amistre64 Group Title

So what would be wrong with this proof by induction?

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I got marked off for some reason

    • 2 years ago
  2. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    what i wrote down on the homework was more like: \[2^n < n! ~;~n\ge4\] basis step: \[2^4 < 4!\]\[16 < 24~;true\] assume \[2^k < k! ~;~k\ge4\] prove: \[2^{k+1} < (k+1)!\]\[2*2^k < k!*(k+1)\]since: \[2 < \{5,6,7,8...\}\hspace{15em}QED\]or \[2^k < k!\frac{(k+1)}{2}\hspace{16em}QED\]

    • 2 years ago
  3. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I don't see anything blatantly wrong with it... I came up with a slightly different argument

    • 2 years ago
  4. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    It hard to determine when proofing means, "reinvent the wheel", or "use common knowledge". But i got marked off 1.5 pts on a 2pt problem

    • 2 years ago
  5. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    What does 2<{5,6,7,8...} mean?

    • 2 years ago
  6. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Oh. You mean 2 is less than any element in that set.

    • 2 years ago
  7. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    right

    • 2 years ago
  8. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[2^k<k!\implies\frac{2^k}{k!}<1\]\[2^{k+1}=2\cdot2^k<(k+1)k!\]\[2\cdot\frac{2^k}{k!}<k+1\]since \(\Large \frac{2^k}{k!}<1\) that implies that \[\Large2\cdot\frac{2^k}{k!}<2<k+1\]since we have assumed that \(k>4\) not sure if your prof would have liked that any better, I'm not so great at induction...

    • 2 years ago
  9. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    thats a fine rendition; my prof would rather have us get it into a form similar to the assumption to compare with tho

    • 2 years ago
  10. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    well I guess you could proceed to multiply both sides by k! again but that seems a bit redundant

    • 2 years ago
  11. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Turing I like that you recalled that k+1>2 since k>=4 So \[2^{k+1}=2^k \times 2 <k! \times (k+1)=(k+1)!\]

    • 2 years ago
  12. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    This proves the thingy

    • 2 years ago
  13. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yes, much more succinct myin :)

    • 2 years ago
  14. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You can say that middle part was by induction when I used 2^k<k!

    • 2 years ago
  15. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Or turing I and turing or interchangeable I guess

    • 2 years ago
  16. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    are*

    • 2 years ago
  17. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    i managed to eke out a 12/10 on the homework nonetheless :)

    • 2 years ago
  18. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    then quit yer whining :P

    • 2 years ago
  19. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You proof starts off with what looks like an assumption that the n+1 case is true, and concludes that 2^k < k! * (k+1)/2 this is true, but you want to prove the case for 2^(k+1) In other words: assume 2^k < k! 2* 2^k < 2* k! (multiply both sides by 2 does not change the relation) 2^(k+1) < 2*k! with 2< (k+1) true for all k>1 2*k! < (k+1)*k! 2*k! < (k+1)! and we have 2^(k+1) < 2*k! < (k+1)! and conclude 2^(k+1) < (k+1)!

    • 2 years ago
  20. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    by modifying: 2^(k+1) < (k+1)! into a form that can be compared against, 2^k < k! we can deduce the truth value. By modifying it into: 2^k < k! * (k+1)/2 Since (k+1)/2 is a positive value that increases k!; and since 2^k doesnt increase at all; then by basic mathing (or logic) skills; an increase in something that is already bigger will remain bigger.

    • 2 years ago
  21. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    at least that has been all the examples that the teacher has done on the board for us

    • 2 years ago
  22. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I think it is the difference between if/then and if and only if? Your conclusion is definitely true, and almost obviously implies "the other direction" but it is not explicitly proving the case.

    • 2 years ago
  23. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    in other words you end up with 2^k < k! * (k+1)/2 but the inductive hypothesis is 2^k< k! so proving 2^k < k! * (k+1)/2 is not very interesting.

    • 2 years ago
  24. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    i agree that its not that interesting :) what of my first idea for the proof; that: 2 < {5,6,7,8,...} ?

    • 2 years ago
  25. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    that is true. But the best way is to assume the inductive hypothesis for k, and show that it implies the truth of the k+1 case

    • 2 years ago
  26. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    i was finally able to parse thru your proofing. I like it.

    • 2 years ago
  27. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    im still unsure as to how mine fails; but thats more a testimony to my ignorance than anyting else :)

    • 2 years ago
  28. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    just out of curiosity since I still have trouble with induction at times, what do you make of my attempt @phi ? (I omitted the first step obviously)

    • 2 years ago
  29. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You are assuming 2^(k+1) < (k+1)!, manipulating this to the form 2^k < k! (k+1)/2, and so proving that if the first is true, the latter is true. This is backwards.

    • 2 years ago
  30. amistre64 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ah, so I should try to work the 2^k < k! up to it, instead of backtracking back down

    • 2 years ago
  31. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ah, so I should try to work the 2^k < k! up to it, instead of backtracking back down yes.

    • 2 years ago
  32. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    @TuringTest when you write the second statement \[2^{k+1}=2\cdot2^k<(k+1)k!\] that is what you are to show. I think I would start with your first statment, and then write down you last statement, and work upwards to the conclusion.

    • 2 years ago
  33. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    but 2<(k+1) since k>=4 and 2<k!

    • 2 years ago
  34. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    oops 2^k<k! *

    • 2 years ago
  35. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I see what you are saying @phi, but though it may not be the most kosher way to do it I don't think that it invalidates the proof

    • 2 years ago
  36. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    But the way you wrote it, you are assuming each step going down implies the truth of going back up (which it is), but the reader is left to figure that out. And it is possible that one of these steps was not reversible. In such a case you may not notice....

    • 2 years ago
  37. TuringTest Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    fair point...

    • 2 years ago
  38. phi Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    And if you write it in the order suggested, it is clear what is being assumed ( 2^k < k! and 2< k+1), and the conclusion follows from simple steps.... very convincing, and it leaves no doubts.

    • 2 years 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.