# Induction problem clarification

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 May 12 '20 at 17:22
• Where is this solution from? May 12 '20 at 17:57
• $k * 6k \leq (k + 10)!$ is clearly a typo. It should be $k*6^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. 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}$. May 12 '20 at 18:15
• Okay, that solution makes no sense at all! Where did you get it from? May 12 '20 at 18:21

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

• Perhaps I am missing something. How do you know that $\;k\times 6^k \;\leq \;(k+10)!$? May 12 '20 at 18:25
• 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)!$. May 12 '20 at 18:29
• @fleablood thanks, I got it now. 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? May 12 '20 at 18:53
• @JevinKosasih It seems ok to me. :) May 12 '20 at 19:01

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