Induction problem clarification

Question

here's the problem I'm doing:

Prove that for all integers $n$ with $n \geq 1$, we have $n \cdot 6^n \leq (n+10)!$

I don't understand how to get from [$6 \cdot (k + 10)! + 6^{k+1}$] to $k \cdot (k + 10)! + 11 \cdot (k + 10)! $.

Base Case:

Let $ n = 1$.

Then, $LHS = 1 \cdot 6 = 6$

$RHS = (1 + 10)!$

Clearly, $6 \leq 10!$ and hence, the inequality is satisfied for the base case.

Inductive Hypothesis:

Let us assume that for $n = k$, we have $k \cdot 6k \leq (k + 10)!$

Inductive Step:

Now, we would need to prove that for $n = k + 1$, the inequality holds true.

Proof:

$= (k + 1) \cdot 6k+1= 6k * 6^{k} + 6^{k+1} \leq 6*(k + 10)! + 6^{k+1} \leq k * (k + 10)! + 11 * (k + 10)! \leq (k + 11)(k + 10)! \leq (k + 11)!$

Welcome to Mathematics Stack Exchange. Here is a mathjax tutorial — J. W. Tanner, May 12 '20 at 17:22
$k * 6k \leq (k + 10)!$ is clearly a typo. It should be $k6^k\le (k+10)!$. That is* your proposition after all. That $n6^n \le (k+10)!$. The value $k*6k = 6k^2$ has nothing to do with anything. — fleablood, May 12 '20 at 18:13
And $(k+1)6^{k+1} = 6^{k+1}k + 6^{k+1} = 6k*6^k + 6^{k+1}$. — fleablood, May 12 '20 at 18:15
Okay, that solution makes no sense at all! Where did you get it from? — fleablood, May 12 '20 at 18:21

score 2 · Answer 1 · answered May 12 '20 at 18:22

2

You can do it more straightfoward. Because you are assuming $k \ge 1$, you have obviously $6^{k} \le k6^{k} \le (k+10)!$. Thus: $$6(k+10)!+6^{k+1} = 6[(k+10)!+6^{k}] \le 6[(k+10)!+(k+10)!] = 12(k+10)! \le (k+11)(k+10)!$$

answered May 12 '20 at 18:22

IamWill

4,025

Perhaps I am missing something. How do you know that $;k\times 6^k ;\leq ;(k+10)!$? – user2661923 May 12 '20 at 18:25
1

Um.... that was the induction assumption... you are trying to prove $n6^n \le (n+10)!$ so you assume it is true for $n=k$. So you assume $k6^k \le (k+10)!$ and try to prove $(k+1)6^{k+1} \le ((k+1) + 10)!$. – fleablood May 12 '20 at 18:29
@fleablood thanks, I got it now. – user2661923 May 12 '20 at 18:41
@IamWill Thanks that definitely clears things up. I also figured out that since k ≥ 1, then 6 ≤ k+5. Also, 6·6^{k} ≤ 6(k+10)!. Thus, 6(k+10)!+6^{k+1} ≤ (k+5)(k+10)!+6(k+10)! = (k+11)! Would that be correct? – intriguedcapy May 12 '20 at 18:53
@JevinKosasih It seems ok to me. :) – IamWill May 12 '20 at 19:01
No problem! What's important is that you solved your question! :) – IamWill May 12 '20 at 19:11

user2661923 · Answer 2 · 2020-05-12T18:42:42.670

I was confused by the OP's work, so I didn't focus that closely on it. Anyway: as $n \to (n+1),$
the LHS increases by a factor of $6\frac{n+1}{n}$
while the RHS increases by a factor of $(n+1).$

For $n \geq 7, \;6\frac{n+1}{n} < 6\frac{n+1}{6} = (n+1).$
Therefore, for $n \geq 7,$ the LHS is increasing by a smaller factor than the RHS.

Thus, you simply have to manually check that the assertion is true for $n \,\in \,\{1,2,3,\cdots,7\}.$

Then, use can use $n=7$ as the base case an apply induction against all $n > 7.$

$\underline{\text{Addendum}}$
IamWill's answer is better than mine, because he found analysis that allows the induction to begin at the base case of $n=1,$ rather than $n=7.$

Induction problem clarification

2 Answers2