Proof by induction

[hard prism]

Prove that n! > n² holds true for all integers of n >= 4

[native cargo]

1. Do not ping the Moderators, unless someone is breaking the rules.
2. Do not ping the Helper Moderators, unless there is a conflict between helpers.
3. Do not ping other members randomly for help.
4. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
5. Wait patiently for a helper to come along.
6. If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:

+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[hard prism]

I'm going to sleep now so I won't reply soon but yea Idk how to start even😭

[sly rose]

It seems like you maybe don't know how proof by induction works?

[torpid bobcat]

The way proof by induction works is as follows

You have some proposition that can either be true or false for a specific integer

Call it P(N)

Induction says that if you prove that P(N)→P(N+1) and that for some N, P(N) works, P(N) will be correct for all of the following ones

In other words it's like dominos

[sly rose]

?tag helping

[versed mural]

**When helping people, please do not dump the full solution. **
Remember that these people are trying to learn concepts, and our goal should be to reinforce them. Giving them a solution will not help.

**Instead, give them hints and guide them toward the correct solution. **
You can ask things like "what part did you get stuck on?" or "what have you tried so far?" or give them a small starting hint. This ensures better learning. For more tips, reach out to Schlaumau (@schlaumau).

[torpid bobcat]

👍

[sly rose]

So probably you should delete all the work you did.

[torpid bobcat]

Most of it was explaining the idea of induction

Which I don't think is telling the solution

[sly rose]

Yes, so delete the bits that aren't.

[torpid bobcat]

Yep

[grave lion]

do not start a help topic and abandon it right away in the hopes of someone doing your work for you

a surefireway to earn yourself this

[hard prism]

Oh okay I won't

[hard prism]

Well I know the steps

First we check base case so in this case

P(4): 4! = 24 and 4^2 = 16 so 24 > 16 so checks out

Then it's

P(k) => P(k+1)

Those are the steps I have written down in my notebook

[hard prism]

Idrk why P(k) implies that P(k+1)

[hard prism]

I kinda understand why it works tho because well if you've proven that the case holds true for some integer k and you've proven that it holds true for k + 1 as well then cuz like

[hard prism]

IT'S HARD FOR ME TO PUT IT INTO WORDS like basically then you can say that k + 1 = m and m is still an integer so it'll hold for m + 1 as well like step 2 says and yea m + 1 = k + 2 so it basically goes on forever

What else I remember I think is that we assume? that k! is in fact > k^2 and like go from there but I don't really understand why we're allowed to assume stuff either

[mighty crag]

okay so typically when proving an implication A -> B you assume A and derive B, from that derivation we derive A -> B; induction here is the inference rule starting from Pk and Pk -> P(k+1) that Pn holds for all n >= k; so when we’re proving, for instance, n! > n^2 for n >= 4 via induction, we let P(n) be "n! > n^2." we prove P4 and then we prove Pk -> P(k+1).

[hard prism]

Okayyy so

Well I was gonna say multiply both sides of k! > k² by (k + 1) so we get (k + 1)! on the left

But the right side has to be in some form that has (k + 1)² in it right

I'm trying to think of something but Idkk

[mighty crag]

okay if you go this route, it suffices to show that (k+1)! > k^3 + k^2 >= (k+1)^2 for k >= 4, so you're just proving k^3 + k^2 >= (k+1)^2 for k >= 4. this isn't much easier but it is slightly easier. do you have any other ideas?

[hard prism]

Well I also squared both sides to get (k + 1)² so I have (k + 1)!(k + 1)! > k⁴(k + 1)² I thought if we solved (k + 1)! = k⁴ we'd get somewhere

I'll read closely what you said thoo

[mighty crag]

yeah but that's going to be pretty hard. my advice is to try and reduce the order of that (k+1)^2 term as much as possible

[hard prism]

After squaring both sides?

[hard prism]

But here how do you know that k³ + k² >= (k + 1)²

[mighty crag]

you don't, you'd have to prove that---it's why i don't recommend this approach

[mighty crag]

no, in the original equation. reduce (k+1)! > (k+1)^2 down to a simpler form, ideally without the squared term on (k+1)^2, and use that to prove (k+1)! > (k+1)^2 assuming k! > k^2.

[hard prism]

So we assumed k! > k² and we're proving that by simplifying (k + 1)! > (k+1)² ?

[mighty crag]

yeah. the idea is that if we can simplify (k+1)! > (k+1)^2 to an equivalent form that we can prove holds, then we've proven (k+1)! > (k+1)^2 since they're equivalent

like a > b is true whenever 2a > 2b is true and only whenever that's true

[hard prism]

But we're proving an assumption based on another assumption why can we do that and it's proof😭

[mighty crag]

well, we're simply proving k! > k^2 implies (k+1)! > (k+1)^2

we also prove independently 4! > 4^2

i think it might be helpful to actually produce out the full proof for you and explain what's happening

[hard prism]

I got the first step on paper P(4): 4! = 24 > 4² = 16

[hard prism]

Here we can just

Divide both sides by (k + 1) right

Wait no

I mean yes but that's not all

I'll try to do it now

Well it's just

k! > k + 1

[mighty crag]

yeah

now you've assumed k! > k^2, so it suffices to show k^2 > k+1

[hard prism]

Okayy

[mighty crag]

do you have any ideas for how you might do that?

[hard prism]

Oh so we don't just assume this inequation and solve it

I was doing that rn😭

[mighty crag]

well, you do assume k! > k^2

now yeah when dealing with these equations you'll find very quickly what you do usually feels like "assuming" it and showing it turns out to imply a true equation, but in reality you're just showing k^2 > k + 1 is equivalent with some other equation that's true

so like k^2 > k + 1 is true whenever and only when k^2 - k > 1 is true, or whenever and only when k^2 - 1 > k is true, or whenever and only whenever k^2 - k - 1 > 0 is true

[hard prism]

It makes sense with this simple inequality yeah

I gott

k1 < 0 and k2 = (1 + sqrt(5))/2

So k2 is smaller than 4

[mighty crag]

alright, i was slightly worried you would see the quadratic and solve it

that does work but it's a bit overkill

there are two, in my opinion, slightly easier techniques you can do

[hard prism]

Ik the viete's formulas but since the answer is irrational it wouldn't be easy would it

[mighty crag]

you can factor k^2 - k and see it's k(k-1) > 1 and note that since k,k-1 are integers that this would always be true for k > 1. or you can factor k^2 - 1 and see it's (k-1)(k+1) and see that this will always be greater than k < k+1 for k-1 >= 1, so k > 1.

[mighty crag]

yeah, i mean computing out the roots of k^2 - k - 1 > 0 does work, it's not a bad solution but it is going to require you calculate the value of (1 + sqrt(5))/2 and do some case work and so i don't recommend it

[hard prism]

Oh yeah maybe it would be hard to show that an irrational is smaller than some number 😭

[hard prism]

Yes makes sensee

So we've shown that P(k) holds true when P(k + 1) hold true right

[mighty crag]

no, the opposite, P(k+1) holds when P(k) does

[mighty crag]

overall it wouldn't be too bad since you can show pretty easily sqrt(5) < 5 and (1+5)/2 = 6/2 = 3 which is still smaller than our desired 4 <= n

[hard prism]

Yess but it'd be hard if it were n => 3 for me😭

At least it'd take time yeah

[hard prism]

Oh okay

I'll look over it all and see if I understand

I think I understand why we did thatt it's because

First we checked the base case cuz well if we check P(k + 1) we need to start somewhere

So if k were 4 and it's true for 4 P(k + 1) will still hold true so P(5) holds true

[hard prism]

And if k were 5 which we know to be true P(6) will still hold true and yes so on

That's right right?

[mighty crag]

yeah

[mighty crag]

that's the idea behind induction, at least

it holds for P4, so it holds for P5, so it holds for P6, so it holds for P7, and so on and so forth

[hard prism]

Yess okayy

Thank you so muchh

I'm glad I got it

+close

[hoary lily]

Please thank your Helpers before closing!

Please thank the helpers who assisted you by clicking the buttons below. You can thank each helper only once. Once you're done, click "Close Post" to close this thread.

[hoary lily]

Thank you for your feedback! (drowsy) dialethic magma has been awarded 1 . They now have 3 . They have 3 daily left for today.