# Prove By Mathematical Induction

• May 30th 2010, 09:59 AM
splbooth
Prove By Mathematical Induction
I'm stuck on this question:

State the principle of mathematical induction, and use it to prove that for \$\displaystyle n \geq 4\$

\$\displaystyle 4n! > 2^{n+2}\$

So far I've done this:

\$\displaystyle P(n)\$ is a statement for each natural number \$\displaystyle n\$, where \$\displaystyle n \geq 4\$. \$\displaystyle P(n)\$ is true if:

• P(n) is true for n = 4.
• If it is true for arbitrary n, it is also true for n + 1.

For \$\displaystyle n = 4\$, \$\displaystyle 4(4!) > 2^{6}\$, \$\displaystyle 96 > 64\$ hence true.

For \$\displaystyle n + 1\$:

\$\displaystyle 4(n + 1)! > 2^{n + 3}\$

\$\displaystyle (n + 1)! > 2^{n + 1}\$

\$\displaystyle n!(n+1) > 2^{n}(n+1)\$ (Using hypothesis)

And that's where I get stuck. RHS should be \$\displaystyle 2^{n+1}\$, but that only occurs when n = 1.

• May 30th 2010, 10:16 AM
Quote:

Originally Posted by splbooth
I'm stuck on this question:

State the principle of mathematical induction, and use it to prove that for \$\displaystyle n \geq 4\$

\$\displaystyle 4n! > 2^{n+2}\$

So far I've done this:

\$\displaystyle P(n)\$ is a statement for each natural number \$\displaystyle n\$, where \$\displaystyle n \geq 4\$. \$\displaystyle P(n)\$ is true if:

• P(n) is true for n = 4.
• If it is true for arbitrary n, it is also true for n + 1.

For \$\displaystyle n = 4\$, \$\displaystyle 4(4!) > 2^{6}\$, \$\displaystyle 96 > 64\$ hence true.

For \$\displaystyle n + 1\$:

\$\displaystyle 4(n + 1)! > 2^{n + 3}\$

\$\displaystyle (n + 1)! > 2^{n + 1}\$

\$\displaystyle n!(n+1) > 2^{n}(n+1)\$ (Using hypothesis)

And that's where I get stuck. RHS should be \$\displaystyle 2^{n+1}\$, but that only occurs when n = 1.

you can try to prove whether or not \$\displaystyle 4(n+1)!>2^{(n+1)+2}\$ if \$\displaystyle 4n!>2^{n+2}\$

P(k)

\$\displaystyle 4k!>2^{k+2}\$

P(k+1)

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

Proof

\$\displaystyle 4(k+1)!=4(k+1)k!=(k+1)4k!\$

If \$\displaystyle k\ge4\$ then \$\displaystyle (k+1)4k!\ge(5)4k!\$

\$\displaystyle 2^{k+3}=(2)2^{k+2}\$

Then if \$\displaystyle 4k!>2^{k+2}\$

\$\displaystyle 4(k+1)!>2^{k+3}\$ certainly since \$\displaystyle (5)4k!>(2)2^{k+2}\$
• May 30th 2010, 10:22 AM
splbooth
That's great, thanks :D