You are here:

Advanced Math/Mathematical Induction

Advertisement


Question
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!

Answer
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.

Advanced Math

All Answers


Answers by Expert:


Ask Experts

Volunteer


Clyde Oliver

Expertise

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.

Experience

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.

©2016 About.com. All rights reserved.