2

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.

Math Major
  • 2,234
  • 2
    If $k\ge 2$ then $k2^k+2^k\gt 2^k+2^k=2^{k+1}$. – André Nicolas Feb 05 '15 at 21:22
  • Strong induction simply means that you assume that the statement is true for all integers from the base case to $k$, then show that the statement is true for $k+1$ also. In weak induction, you only assume the statement at $k$ to show the statement is true at $k+1$ – Joffan Feb 06 '15 at 00:31

3 Answers3

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.

Joffan
  • 39,627
  • 4
    The awkwardness is because of the unfortunate (and wrong) school habit of proving $A=B$ or $A\gt B$ by starting from the conclusion and manipulating until one gets something true. – André Nicolas Feb 05 '15 at 21:25
2

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.

Daniel W. Farlow
  • 22,531
1

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

Aaron Maroja
  • 17,571