Why in induction (n+1)! becomes (k+1)!a instead of (k+1+1)!?

Question

I am just starting induction and I am having a problem understanding why is this possible.

Here is an example:

Prove that $3^{n} < (n + 1)!$ for $n \geq 4$ and $n \in \mathbb{N}$.

This is how I start:

Basis case: n = 4 then $3^{4} < (4 + 1)!$ (Sparing the mental math) is true!

Then inductive hypothesis:

Assume that $3^{k} < (k + 1)!$ is true for some $k \in \mathbb{N}$ and $k \geq 4$.

Inductive step:

if $n = k$ is true $n = k + 1$ is also true. So

$3^{k+1} = 3^{k} \cdot 3 = 3^{k} + 3^{k}$

Now I am stocked the person goes on and says:

$3^{k} \cdot 3 < (k + 1)! \cdot 3$ but why so?! should it it be $3^{k} \cdot 3 < (k + 1 + 1)!$ (aka $(k + 2)$) because we are replacing the k with $k+1$?

Answer 1

That is what you have to obtain ultimately. But you didn't state the inductive step correctly. It should be: ‘If $n=k$ is true, then $n=k+1$ is too’ (in other words: one case implies the next case, not the previous one).

So you make the hypothesis that for some $k\ge 4$, $3^k<(k+1)!$ and you have to deduce that $3^{k+1}<(k+2)!$. Now the inductive hypothesis implies, multiplying both sides of the inequality by $3$: $$3^k\cdot3=3^{k+1}< (k+1)!\cdot 3$$ From $k\ge 4$, you deduce $k+2>k>3$, so $$3^{k+1}< (k+1)!\cdot 3<(k+1)!\cdot(k+2)=(k+2)!$$

Answer 2

$3^{k} \cdot 3 < (k + 1)! \cdot 3$ must be true if you are assuming

$3^{k} < (k + 1)! $

You are simply multiplying by three on both sides of the inequality.

Answer 3

Yes, you are right! It could be writen as follows: \begin{equation} ¿3^k < (k+1)! \implies 3^{k+1} < (k+2)!? \end{equation} \begin{equation} 3^{k+1} = 3·3^{k} < 3·(k+1)! < (k+2)·(k+1)! = (k+2)! \end{equation} The last inequality is because $k\geq4$.