You are here:

- Home
- Science
- Mathematics
- Advanced Math
- Mathematical Induction

Advertisement

I am practicing this question for a test.

Prove that n!>2^n for every positive integar n.

This is the proof I have written, but I am not sure I did it right and there is probably a more elegant way to to this.

Proof: Induction on n

Step: Let n=4. Then

n!>2^n

=4x3x2x1>2^4

=24>16.

Base:

Assume that k!>2^k for integars greater or equal to 4.

Now replacing k with k+1,

we have (k+1)!>2^(k+1)

=(k+1)(k!)>2x2^k.

Since k is greater or equal to 4, k+1>2 and

k!>2^k can be expressed as

kx(k-1)x...x4x3x2x1 > 2x2x2x2x(2^k-4).

Since 4x3x2x1=24 > 2x2x2x2=16,

and (k)(k-1) > 2^(k-4), then k!>2^k.

Now we observe that k!>2^k and

k+1 > 2, so the product of k!(k+1) is

greater than the product of (2)(2^k).

I'm not sure if this even shows induction or if it even proves this so if you could help me out that would be great! Thanks!

First, you say "for every positive integer n" when you probably mean "for ever integer n≥4." This statement is not true for n=1,2,3.

You show the base case 4, but you don't apply induction correctly -- you're making it too complicated. All you need to do is this:

Assume it is true for n=k, so that:

k! > 2^k

Now consider that:

(k+1)! = (k+1) × k!

By the induction assumption:

(k+1)! = (k+1) × k! > (k+1) × 2^k

And because k > 4, k+1 is definitely greater than 2, so:

(k+1)! = (k+1) × k! > (k+1) × 2^k > 2 × 2^k = 2^(k+1)

That one line sums up the entire induction step of the proof.

- Add to this Answer
- Ask a Question

Rating(1-10) | Knowledgeability = 10 | Clarity of Response = 8 | Politeness = 10 |

Comment | No Comment |

Advanced Math

Answers by Expert:

I can answer all questions up to, and including, graduate level mathematics. I am more likely to prefer questions beyond the level of calculus. I can answer any questions, from basic elementary number theory like how to prove the first three digits of powers of 2 repeat (they do, with period 100, starting at 8), all the way to advanced mathematics like proving Egorov's theorem or finding phase transitions in random networks.

I am a PhD educated mathematician working in research at a major university.**Organizations**

AMS**Publications**

Various research journals of mathematics. Various talks & presentations (some short, some long), about either interesting classical material or about research work.**Education/Credentials**

BA mathematics & physics, PhD mathematics from a top 20 US school.**Awards and Honors**

Various honors related to grades, various fellowships & scholarships, awards for contributions to mathematics and education at my schools, etc.**Past/Present Clients**

In the past, and as my career progresses, I have worked and continue to work as an educator and mentor to students of varying age levels, skill levels, and educational levels.