Proof by Induction: $∀n ≥ 5, 2^n + 2n < n!$

Question

I'm having trouble understanding how to solve this question.

Proof by induction: $∀n ≥ 5, 2^n + 2n < n!$

I don't understand how they got those steps that I highlighted in the picture attached below.

Any help is appreciated.

Thanks!

Answer 1

You are assuming $2^k + 2k < k!$ and tring to prove $2^{k+1} + 2(k+1) < (k+1)!$. Because you are assuming $2^k + 2k < k!$ then $$2^k + 2k < k! \Rightarrow 2(2^k + 2k) < 2(k!) \Rightarrow 2(2^k + 2k) +2 < 2(k!) + 2$$

and this is the first highlighted step.

For the second one, because $k\geq 5$ (so $k>2$):

$$2(k!)+2 < 2(k!) + k! < 3(k!) < (k+1)(k!)$$

Answer 2

So first, we need to understand what does one actually do, in induction we first assume that the hypothesis is true for some iteration $k$ and then show that it also holds for $k+1$. After we have checked for some particular value and followed the above step, induction says that the statement is true for any iteration.

We have: $\forall\ n\ge 5$, W.T.S. $2^n+2n < n!$. First, see that for $n= 5, 2^5 + 2\cdot 5 = 32+10 = 42 < 5! = 120$. So the statement is true for some value, namely $5$. Next, we assume it to be true for $n = k$, and try to show for $n =k+1$.

$2^{k+1}+ 2(k+1) = 2\cdot 2^k + 2k +2 < 2(2^k+2k)+2 < 2k! + 2$ (because we assumed that statement is true for $k$) $< 2k! + k!$ (since $k\ge 5$) <3k! < (k+1)! Hence we prove the statement for $n =k+1$ and hence it is true for all $n$ by induction.

Hope this helps.