Proof by Induction that: $n!>3^n$ for $n>6$

Question

Okay, I have this question: $n! > 3^n$, $6<n\in\mathbb Z$
Now, I solved it easily, but the answer is giving me trouble.
base - $n=7$, good.
assumption: $k! > 3^k$
Proof: $(k+1)! > 3^{k+1}$
Okay, played a little, got to this:
$k! \cdot (k+1) > 3^k \cdot 3$
lastly, got to:
$k>2$ Which gives me problem. I know k=n is greater than 6 (as said in the question).
But k is not greater then 2, it is greater than 6(not included).
Isnt this a contradiction?? I searched here for this solution as I got stuck, saw a few answers, others had $k>2$ the same as me and that is how they ended the question... Which is not a good answer, as I said, k is greater than 6, not than 2.... How am I continuing here from the solution I got?

EDIT: Okay, I saw people had trouble with my question. My question is: why the answer K>2 is good for this solution? since n>6 and k=n, so K should be also k>6. K=3,4,5,6 doesnt exist, but if I put k>2, it does exist.

Second Edit(Final): Managed to solve it, thanks to @Eric Towers.

Hint: after you assumed that $k!>3^k$ you should then multiply both sides by $k+1$ — Mufasa, Nov 04 '21 at 20:21
“I solved it easily, but the answer is giving me trouble.” Doesn’t sound “easily” to me, then. — Thomas Andrews, Nov 04 '21 at 20:22
uh.. look at my answer... it should be correct, look at the whole message, I got the same as others, but it doesnt satisfy me.. its not complete, where is the mistake??? — , Nov 04 '21 at 20:22
You already know $k>6$. What's the smallest value for $k$, the one in the base case? — Eric Towers, Nov 04 '21 at 20:23
@Mufasa look at the whole post, I got to a good answer, look exactly — , Nov 04 '21 at 20:23
@EricTowers base case n=7... Guys, Look at the whole post.. I solved it, look at the solution, dont just look on title or first line of the problem, look at what I wrote... — , Nov 04 '21 at 20:24
@ThomasAndrews why? k=3 works? no, k=4 works? no, it cant be the solution. its not logic... — , Nov 04 '21 at 20:24
Welcome Ben. Your question is sloppily written; do try not to get impatient with the responders — FShrike, Nov 04 '21 at 20:24
We are trying to make sense of what you have written, but it is not presented in a manner that is directly understood. You appear to be baffled that $k > 6$ implies $k > 2$, but it is hard to (1) determine if this is actually what you intend to ask about or (2) whether this is actually what is stopping you. — Eric Towers, Nov 04 '21 at 20:25
@FShrike why sloppily written? the question it written perfectly, k! > 3^k, k>6, thats the question, nothing else. My problem is only about k>2. its not being impatient, its just that I write all the stages of the solution, and I solved it, but people dont read the whole post — , Nov 04 '21 at 20:26
$k=3$ does not satisfy $k>6.$ If $k>6$ then $k>2.$ We do not have the converse, “If $k>2$ then $k>6.$” But you don’t need that. — Thomas Andrews, Nov 04 '21 at 20:27
I don’t know what you don’t understand. What do you think “If $k>6,$ then $k>2” means? Do you know what a converse is? — Thomas Andrews, Nov 04 '21 at 20:29
converse? no idea really ( maybe in my own laugage I can understand ), I will check. — , Nov 04 '21 at 20:31
Converse is basically like "reverse", or "opposite", in this context. Elsewhere in English, converse (emphasised a little differently) means to speak; like "conversation". @ThomasAndrews Means that the converse to $k\gt6\implies k\gt2$ is the reverse statement, loosely, i.e. $k\gt2\implies k\gt6$, but this converse isn't true — FShrike, Nov 04 '21 at 20:33

score 1 · Accepted Answer · edited Dec 23 '22 at 13:18

1

Have: $k! > 3^k$ for some particular $k > 6$.

Want: $(k+1)!>3^{k+1}$

Proof:
$$ (k+1)! = (k+1)k! > (k+1)3^k > (6+1)3^k\\ = (7)3^k > (3)3^k = 3^{k+1} \text{.} $$ Therefore, $(k+1)! > 3^{k+1}$, as desired.

At $(1)$, we use $k > 6$ so $k+1>6+1$, and then, since $3^k > 0$, $(k+1)3^k > (6+1)3^k$. At $(2)$, we use $7 > 3$ and $3^k > 0$, so $(7)3^k > (3)3^k$. In both cases, we use $a > b$ and $c > 0$ implies $ac > bc$.

edited Dec 23 '22 at 13:18

Toby Mak

16,827

answered Nov 04 '21 at 20:32

Eric Towers

67,037

OP's confusion is not about the proof itself, but about why the statement requires $k>6$ if the proof of the inductionstep also works with $k>2$. – Student Nov 04 '21 at 20:35
@Student : It's right there in the first line. The base case is mute for $k \leq 6$. – Eric Towers Nov 04 '21 at 20:36
Hi, then can you tell me what am I supposed to write at the explanation? usually after I write the induction and get to the proof itself, I write things to explain my calculations and such. but here its a little problematic. – Nov 04 '21 at 20:37
I know, but OP somehow/falsely assumed that such conditions always need to strictly hold for both steps. – Student Nov 04 '21 at 20:37
@Student Exactly, I never heard of such an induction before, was never taught such a thing exists – Nov 04 '21 at 20:39
@BenShaines : If you can write an induction starting at $3$, you can write an induction starting anywhere after $3$. This induction starts at $n = 7$, so in the inductive hypothesis, we must have $k >6$ because nothing that has come before in the proof speaks to $k \leq 6$. – Eric Towers Nov 04 '21 at 20:40
@EricTowers Yea, I understand this, that the base case( K > 6 ) doesnt have to go side by side with the conclusion ( K > 2). but I still dont know what am I supposed to write as an explanation, its really confusing... I need to explain it somehow, but no idea how to. – Nov 04 '21 at 20:41
The base case is not $k > 6$. The base case (the one you wrote) is $n = 7$. Consequently, the smallest $k$ that is permissible in your inductive hypothesis is $k = 7$. I have exactly recited what your proof in the inductive step is, including (1) what you failed to write in your hypothesis, and (2) where that condition is used in the proof. You have yet to explain what is faulty in my proof. – Eric Towers Nov 04 '21 at 20:43
@EricTowers I never said it was faulty, but I cant really also understand it, I was also never taught I can put numbers instead of variables at the induction, like you did with (7)3^k and then the (3)3^k, didnt really understand it... I dont think my question should be that complicated. – Nov 04 '21 at 20:46
Can you maybe make it more understandable with words? what you did each step starting from line 3 of proof? – Nov 04 '21 at 20:47
@BenShaines : Your base case is the case $n = 7$. Your inductive step goes from $k$ to $k+1$. The smallest choice of $k$ consistent with your base case is $k = 7$, that is, $k > 6$. You failed to write that in your inductive hypothesis so your incomplete inductive hypothesis is confusing you. That condition is available to you in your proof. Surely you know the inequality fact $a > b$ and $c > 0$ implies $a c > b c$. Since $3^k > 0$, we have both inequalities you comment on. – Eric Towers Nov 04 '21 at 20:49
about - failed to write: I didnt, i did write base case n=7, and that k>6 ( or you mean at the base induction stage? I never write the k>something at base, wasnt taught like that ). About what you did with a>b and such, i understand ac>bc, but cant understand how it relates to $3^k$. I understand I am really bad in math if I cant understand this.. uhh, its frustrating... – Nov 04 '21 at 20:53
@BenShaines : "assumption: $k!>3^k$" does not have "$k > 6$", which is required by your base case. If your base case were $n = 100$, you would have $k \geq 100$ in the assumption for your induction. – Eric Towers Nov 04 '21 at 20:54
@BenShaines: I've added a bit more about the inequalities to the end of the discussion. – Eric Towers Nov 04 '21 at 20:56
Yea, I just noticed. thanks. I guess I will try to ask a friend or my teacher... I really cant seem to understand this thing. I wont dig in your mind anymore, thanks guys for the help :) – Nov 04 '21 at 20:58
@BenShaines : Hold on... (This will take a few back and forths.) What integer does your base case address? – Eric Towers Nov 04 '21 at 20:59
n>6, but the minimum is n=7. ( only completes one ). – Nov 04 '21 at 21:00
@BenShaines : When you apply the inductive step only once to $7$, what integer do you get? (I.e., what new integer do we discover the inequality holds for?) – Eric Towers Nov 04 '21 at 21:01
what do you mean new integer that I get? you mean K+1? , so the inductive step will be k+1>7 – Nov 04 '21 at 21:02
@BenShaines : We know the inequality holds for $n = 7$. Using the inductive step once, we discover it is true for what new choice of $n$? – Eric Towers Nov 04 '21 at 21:03
after I find K>2? or you mean n=8? ( the n+1, so instead of 7, I will get 8 ) – Nov 04 '21 at 21:05
@BenShaines : Yes, appyling the inductive step once, we find that the inequality holds for $n = 8$. Now apply the inductive step again. We discover the inequality holds for what new choice of $n$? – Eric Towers Nov 04 '21 at 21:06
n=9 and then n=10 and then n=10+new... – Nov 04 '21 at 21:07
@BenShaines : Okay... What is the smallest choice of $k$ that is compatible with using the inductive step on the $n$s: $7$, $8$, $9$, $10$, ... – Eric Towers Nov 04 '21 at 21:07
$n>6$ or $n>=7$ – Nov 04 '21 at 21:09
@BenShaines : Agreed. Does our induction ever attempt to show that the inequality holds for $n = 6$ or $n = 5$ or any lesser choice of $n$? – Eric Towers Nov 04 '21 at 21:09
no, i didnt attempt to it, because base case is n>6. – Nov 04 '21 at 21:10
@BenShaines : So, do we care what happens for $n$s that are less than or equal to $6$? Likewise, do we care what happens if we apply the inductive step for a $k \leq 6$? – Eric Towers Nov 04 '21 at 21:11
no. So after all of this, I got to a conclusion: although the "answer" ( in purpose the "") is n>2, I write that although I got n>2, since base case is n>6, the answer is n>6. – Nov 04 '21 at 21:12
@BenShaines : Not quite. Since we only care about the inequality when $n > 6$, we (1) show the base case for $n = 7$, (2) show the inductive step works for every choice of $k \geq7$, because we do not care what happens if we apply the induction to smaller choices of $k$. But we always have $k \geq 7$ available to us to use in our proof. Agree that $k \geq 7$ implies $k > 2$, but we already know we don't care about the choices $k = 3$, $k = 4$, $k = 5$, and $k = 6$ that sit between these two inequalities. – Eric Towers Nov 04 '21 at 21:14
Okay, I think I understand it, the only problem is how to explain it mathematic way. Although your explanation seems pretty good, I cant say we dont care about the choices, I can say I can neglect the k which are lower then 7 because of the base case, thus the answer is n>7 – Nov 04 '21 at 21:18
@BenShaines : I'd modify your inductive assumption to include $k \geq 7$ or $k > 6$, that is, we only care that the inductive step works for choices of $k$ greater than or equal to the base case. Then use that inequality in some way to complete your proof of the inductive step. For instance, if you have shown the inequality holds if $k > 2$ and you know that $k \geq 7$, then you are done. – Eric Towers Nov 04 '21 at 21:19
Ohhh, I see what you say, when I wrote the answer here, I didnt write the full answer, of course, in my notebook I include for each K>6 k∈Z. sorry, I forgot to mention it. Alright then, I got the answer. Thank you so much for sitting with this thoroughly with me!! really appreciated!! – Nov 04 '21 at 21:22
@BenShaines : Glad to help! Happy mathing! – Eric Towers Nov 04 '21 at 21:22
Thanks!!! ...... – Nov 04 '21 at 21:24

Student · Answer 2 · 2021-11-04T20:32:00.110

0

As $k > 6$, you have that $k+1 > 7 > 3$, which implies that

$$k! \cdot (k+1) > 3^k \cdot 7 > 3^k \cdot 3 = 3^{k+1}.$$

The reason that you have to assume that $k > 6$ is for your base case, since $6! = 720 < 3^6 = 729$, whereas $7! = 5040$ and $3^7 = 2187$, showing that $k = 7$ is the first value where the inequality actually holds.

Note that restrictions on values of $k$ in proofs by induction are not always required in both basecase and inductionstep. Sometimes (like in this proof here), restrictions are only needed for the base case.

edited Nov 04 '21 at 20:32

answered Nov 04 '21 at 20:27

Student

4,438

Thanks, that I understand, but still. Why is K>2 the right answer, although the base case works with k>6 only? Its the first time I see a question like that, that the base case doesnt go with the solution. – Nov 04 '21 at 20:30
$k>2$ the the “right answer” to what? It isn’t the right answer to this question. @BenShaines – Thomas Andrews Nov 04 '21 at 20:31
then what is the right answer? where was my mistake in the calculation? – Nov 04 '21 at 20:32
To Student, just saw the edit: I see... its my first time seeing a induction which has base case higher then the final answer, I solved many induction, but seeing this is a first timer, good I saw it when I practice and not when was on test or something like that... Thanks. – Nov 04 '21 at 20:33
@ThomasAndrews I guess OP does not understand why the question asks to prove the property for $k>6$ if $k>2$ also would work in the induction hypothesis. OP: As I explain in my 2nd paragraph, the restriction is only (and only) required for the basecase. – Student Nov 04 '21 at 20:33

score 0 · Answer 3 · answered Nov 04 '21 at 20:36

0

I'm assuming that what you did to get to $k > 2$ worked along these lines:

Assume $k! > 3^k.$ Then, $(k + 1)! > 3^{k + 1}$ at least whenever $k + 1 > 3 \leftrightarrow k > 2.$

The form of your argument is valid, but it only applies to the induction step of your proof when we can assume $k! > 3^k.$ For $k \leq 6$ this initial assumption doesn't hold, so our proof that $(k+1)! > 3^{k+1}$ doesn't go through. Remember, the conclusion of an argument is only guaranteed if the argument's form is valid and its premises are true.

Instead we need the base case, which we start at $k = 7,$ and then your logic proves it for any $k > 7.$ Hence, it's true for any $k \geq 7 \leftrightarrow k > 6.$ (since $k$ is an integer)

answered Nov 04 '21 at 20:36

Stephen Donovan

5,163

Okay, I understand this, but I still dont know what am I supposed to write as an explanation, this circumstances, first time seeing this.. never knew such an induction that basecase andd proof doesnt go side by side.... – Nov 04 '21 at 20:38
I don't think you should have to change much, I think you might just have to remember what your goals are here. For our induction step we have $k > 6$ and we want to prove $P(k) \to P(k+1).$ You've proven $P(k) \to P(k+1)$ at least whenever $k > 2,$ so if $k > 6$ and $6 > 2$ we must have $k > 2$ so $P(k) \to P(k + 1).$ (I would recommend something more like what Eric Towers' answer shows, but if you want to rework what you have then this should be serviceable) – Stephen Donovan Nov 04 '21 at 20:46
Ahh, I cant understand this... the explanation is weird to me, that k > K+1 works when k>2. its like the f>t is true, its logic is weird... same logic here... ( atleast to me ) – Nov 04 '21 at 20:48
@BenShaines Maybe it will help to think of it this way: it's common to think about induction like knocking over dominoes, in that once you push one, each domino knocks over the one in front of it. Now imagine that I set up a line of dominoes, but pushed over one in the middle of the line. Naturally, although the dominoes before the one I pushed would have fallen had I pushed one before them, they won't fall if I push one after them. Our situation is similar: you've shown that the earlier dominoes would have fallen, but the one that actually gets pushed is further down the line. – Stephen Donovan Nov 04 '21 at 20:52
I understand, but still cant understand how am I supposed to explain this paradox ( atleast to me ). I seriously cant understand what I dont understand about it... – Nov 04 '21 at 20:55
If you don't know what confuses you about it then it's going to be difficult for me to figure it out. Do you think you could try to find a way to explain it, or maybe give an example of an inductive proof that you've seen before which you understood better? – Stephen Donovan Nov 04 '21 at 20:58
Ahh, its all good, I will ask my teacher about it. I cant seem to understand it and I dont want to dig in your mind anymore... But anyway, just so I answer your question: I understand the domino image to the induction. but I cant seem to understand how it relates to the question itself. But really, its all good, thanks. – Nov 04 '21 at 21:00

Proof by Induction that: $n!>3^n$ for $n>6$

3 Answers3