Open study

is now brainly

With Brainly you can:

  • Get homework help from millions of students and moderators
  • Learn how to solve problems with step-by-step explanations
  • Share your knowledge and earn points by helping other students
  • Learn anywhere, anytime with the Brainly app!

A community for students.

So what would be wrong with this proof by induction?

See more answers at
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly


Get your free account and access expert answers to this and thousands of other questions

I got marked off for some reason
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\]
I don't see anything blatantly wrong with it... I came up with a slightly different argument

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

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
What does 2<{5,6,7,8...} mean?
Oh. You mean 2 is less than any element in that set.
\[2^k4\) not sure if your prof would have liked that any better, I'm not so great at induction...
thats a fine rendition; my prof would rather have us get it into a form similar to the assumption to compare with tho
well I guess you could proceed to multiply both sides by k! again but that seems a bit redundant
Turing I like that you recalled that k+1>2 since k>=4 So \[2^{k+1}=2^k \times 2
This proves the thingy
yes, much more succinct myin :)
You can say that middle part was by induction when I used 2^k
Or turing I and turing or interchangeable I guess
i managed to eke out a 12/10 on the homework nonetheless :)
then quit yer whining :P
  • phi
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)!
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.
at least that has been all the examples that the teacher has done on the board for us
  • phi
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.
  • phi
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.
i agree that its not that interesting :) what of my first idea for the proof; that: 2 < {5,6,7,8,...} ?
  • phi
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
i was finally able to parse thru your proofing. I like it.
im still unsure as to how mine fails; but thats more a testimony to my ignorance than anyting else :)
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)
  • phi
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.
ah, so I should try to work the 2^k < k! up to it, instead of backtracking back down
  • phi
ah, so I should try to work the 2^k < k! up to it, instead of backtracking back down yes.
  • phi
@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.
but 2<(k+1) since k>=4 and 2
oops 2^k
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
  • phi
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....
fair point...
  • phi
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.

Not the answer you are looking for?

Search for more explanations.

Ask your own question