Help with factorial inequality induction proof: $3^n + n! \le (n+3)!$

Question

So I'm asked to prove $3^n + n! \le (n+3)!$, $\forall \ n \in \mathbb N$ by induction. However I'm getting stuck in the induction step.

What I have is:

(n=1)

$3^{(1)} + (1)! = 4$ and $((1) + 3)! = (4)! = 24$

So $4 \le 24$ and the statement holds for n = 1.

(n -> n=1)

Assume $3^n + n! \le (n+3)!$ for some $n \in \mathbb N$

So I get $3^n + 2 \cdot 3^n + n!(n + 1)$ and on the RHS $(n + 4)(n + 3)!$ but I can't think/find any way to reduce/manipulate either side by multiplying or adding anything.

The only help my professor gave was:

see if this helps: if $a + b \lt c$ and $a \gt 0$ and $b \gt 0$ then $a \lt c$ and $b \lt c$

But I can't figure out how that helps out either. Thanks in advance for any help and I hope I didn't mess up my first post here.

Answer 1

Prove it for $n=1$ and $n=2$ by hand and do the inductive step when $n\geq 2$:

We want to check

$3^n+3^n+3^n+(n+1)n!\leq (n+4)(n+3)!$

Of course $3^n+3^n+3^n+(n+1)n!\leq(n+1)(3^n+n!)$ since $n\geq 2$.

and $3^n+n!\leq (n+3)!$ by the inductive hypothesis. So we conclude:

$(n+1)(3^n+n!)\leq (n+1)(n+3)!$.

But clearly $(n+1)(n+3)!\leq (n+4)(n+3)!$

Following our chain of inequalities we have:

$3^n+3^n+3^n+(n+1)!\leq (n+1)(3^n+(n+1)!)\leq (n+1)(n+3)!\leq (n+4)(n+3)!$

Answer 2

The proof for n = 1 is correct.

Now, let's go on to the inductive step. Let us consider that $\color{blue}{3^n + n!} \le \color{green}{(n+3)!}$ holds true for some integer n. Then the next step is to check what happens to the inequality for some integer n+1:

$3^{n+1}+(n+1)!=$
$3 \times 3^n + (n+1) \times n!=$
$(3^n + 3^n + 3^n) + \underbrace{n! + ... + n!}_{n+1 \space times}=$
$3^n+n!+3^n+n!+3^n+n!+\underbrace{n! + ... + n!}_{n+1-3 \space times}=$
$3 \times (\color{blue}{3^n + n!}) + \underbrace{n! + ... + n!}_{n-2 \space times}=$

Now substituting the inequality obtained for n,
$\le [3 \times \underbrace{\color{green}{(n+3)!}}_{replacement\space holds \space true}] + (n-2)n!$
$\le [(n+4)(n+3)!]$, since $(n+4)(n+3)! \gt \frac{(n-2)n!}{3}$, as n > 1
$\le (n+4)!$
QED