# difficulty following proof by induction

• Nov 17th 2011, 11:29 AM
Jskid
difficulty following proof by induction
This is given as an example of proof by induction. Prove that \$\displaystyle n! > 2^n\$ for all n >= 4

\$\displaystyle n_0=4\$ and \$\displaystyle 4!=24>16=2^4\$. Thus \$\displaystyle n_0\$ is true. Now suppose that k >= 4 and the statement is true for n=k. Thus we suppose \$\displaystyle k! > 2^k\$ We must prove that the statement is true for n=k+1; that is, we must prove that \$\displaystyle (k+1)! > 2^{k+1}\$. Now
\$\displaystyle (k+1)!=(k+1)k!>(k+1)2^k\$
using the induction hpothesis. Since k >= 4 certainly k+1 > 2 so \$\displaystyle (k+1)2^k>2 x 2^k = 2^{k+1}\$. We conclude that \$\displaystyle (k+1)! > 2^{k+1}\$ as desired. By the principle of mathematical induction we conclude that \$\displaystyle n!>2^n\$ for all integers n>=4

I don't get the part after "certainly k+1>2". What happened to the factorial?
• Nov 17th 2011, 12:17 PM
DrSteve
Re: difficulty following proof by induction
It doesn't say that. It says k+1>2 which it is because k is at least 4. In fact, k+1>4, but all that's needed for the proof is k+1>2.

Also you have a typo. That minus sign towards the end should be an equal sign.
• Nov 17th 2011, 08:13 PM
Jskid
Re: difficulty following proof by induction
Ok but how does that show anything about (k+1)!?
• Nov 17th 2011, 08:25 PM
Prove It
Re: difficulty following proof by induction
Quote:

Originally Posted by Jskid
Ok but how does that show anything about (k+1)!?

You know \$\displaystyle \displaystyle (k + 1)! = (k + 1)k! > (k + 1)2^k\$ and you have shown \$\displaystyle \displaystyle (k + 1)2^k > 2^{k + 1}\$.

Therefore \$\displaystyle \displaystyle (k + 1)! > 2^{k + 1}\$.