News

About

Prizes

Problems & Solutions

Scores

Archive

Links

Problem 5

Prove by induction that

n! > 2ⁿ for n > 3

Solution

Proof by Induction:

Base Case:
n = 4
(4)! > 2⁴ ===> 24 > 16 Which is true.

We will assume that n! > 2ⁿ for all n > 3.

Now we want to show that (n+1)! > 2⁽ⁿ⁺¹⁾ holds true based on the assumption.

We know that (n+1)! = (n+1)*n! and we also know that 2⁽ⁿ⁺¹⁾ = 2ⁿ*2.

Therefore we can rewrite the problem as the following
(n+1)! > 2⁽ⁿ⁺¹⁾ ====> (n+1)*n! > 2*2ⁿ

From the assumption we are assuming that n! > 2ⁿ making the problem
(n+1)*n! > 2*2ⁿ ====> (n+1) > 2 and since n > 3 we know this will always be true.

Thus n! > 2ⁿ for all n > 3.

Q.E.D.