0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Welcome to Mathematics Stack Exchange. Here is a mathjax tutorial $\endgroup$ May 12 '20 at 17:22
  • $\begingroup$ Where is this solution from? $\endgroup$
    – IamWill
    May 12 '20 at 17:57
  • $\begingroup$ $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. $\endgroup$
    – fleablood
    May 12 '20 at 18:13
  • $\begingroup$ And $(k+1)*6^{k+1} = 6^{k+1}*k + 6^{k+1} = 6k*6^k + 6^{k+1}$. $\endgroup$
    – fleablood
    May 12 '20 at 18:15
  • $\begingroup$ Okay, that solution makes no sense at all! Where did you get it from? $\endgroup$
    – fleablood
    May 12 '20 at 18:21
2
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.