amistre64 Group Title So what would be wrong with this proof by induction? one year ago one year ago

1. amistre64 Group Title

I got marked off for some reason

2. amistre64 Group Title

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$

3. TuringTest Group Title

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

4. amistre64 Group Title

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

5. myininaya Group Title

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

6. myininaya Group Title

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

7. amistre64 Group Title

right

8. TuringTest Group Title

$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...

9. amistre64 Group Title

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

10. TuringTest Group Title

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

11. myininaya Group Title

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)!$

12. myininaya Group Title

This proves the thingy

13. TuringTest Group Title

yes, much more succinct myin :)

14. myininaya Group Title

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

15. myininaya Group Title

Or turing I and turing or interchangeable I guess

16. myininaya Group Title

are*

17. amistre64 Group Title

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

18. TuringTest Group Title

then quit yer whining :P

19. phi Group Title

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)!

20. amistre64 Group Title

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.

21. amistre64 Group Title

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

22. phi Group Title

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.

23. phi Group Title

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.

24. amistre64 Group Title

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

25. phi Group Title

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

26. amistre64 Group Title

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

27. amistre64 Group Title

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

28. TuringTest Group Title

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)

29. phi Group Title

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.

30. amistre64 Group Title

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

31. phi Group Title

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

32. phi Group Title

@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.

33. myininaya Group Title

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

34. myininaya Group Title

oops 2^k<k! *

35. TuringTest Group Title

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

36. phi Group Title

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....

37. TuringTest Group Title

fair point...

38. phi Group Title

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.