Induction proof, greater than

Question

Prove that: $n!>2^n$ for $n \ge 4$.

So in my class we are learning about induction, and the difference between "weak" induction and "strong" induction (however I don't really understand how strong induction is different/how it works.

Here's my attempt:

Let S(n) be the statement $n!>2^n$ for $n \ge 4$. Then let n=4

$$4!>2^4$$ $$24>16$$

so S(1) is true. Next, suppose that k is any integer with $k \ge 4$ such that S(k) is the statement $k!>2^k$. Then, multiplying (k+1) to both sides:

$$k!>2^k$$ $$k!(k+1)>2^k(k+1)$$ $$(k+1)!>k2^k+2^k$$

And this is where I am stuck.... S(k+1) is the statement $(k+1)!>2^(k+1)=2*2^k$ so then $k!(k+1)>2^k(k+1)>2*2^k$ because $k \ge 4$? Is this the right thinking, and if so, I am still not really sure how to formally write this out.

Answer 1

For $n\geq 4$, denote the statement involving $n$ by $$ S(n) : 2^n<n!. $$ Base step ($n=4$): Since $2^4=16$ and $4!=24$, the statement $S(4)$ is true.

Inductive step: Fix some $k \geq 4$ and assume that $$ S(k) : 2^k < k! $$ is true. To be shown is that $$ S(k+1) : 2^{k+1} < (k+1)! $$ follows. Beginning with the left side of $S(k+1)$, \begin{align} 2^{k+1} &= 2(2^k)\\[0.5em] &< 2(k!)\tag{by $S(k)$}\\[0.5em] &< (k+1)(k!)\tag{since $k\geq 4$}\\[0.5em] &= (k+1)!, \end{align} the right side of $S(k+1)$. This concludes the inductive step $S(k)\to S(k+1)$.

Thus, by mathematical induction, for all $n\geq 4$, the inequality $S(n)$ is true.

Answer 2

You're so close... all you need is $$ (k+1)!>k2^k+2^k>2^k+2^k=2^{k+1}$$

Earlier you lay out your demonstraion of the inital induction condition slightly awkwardly; I would say: $$ 4!=24>16=2^4$$ which reading left to right makes unremarkable claims at each step and finishes with the required inequality.

Answer 3

Hint: Notice that $k 2^k > 2^k$, for $k \geq 2$.