I am trying to prove that n! > 2^n for n>3. I figure this sort of proof needs induction, but I am stuck.

Question

1. Base case n = 4
4! = 24
2^4 = 16
24 > 16

2. Assume n!>2^n. Prove (n+1)!>2^(n+1)
n! > 2^n
2*(n+1)n! > (n+1)(2^n)*2
2(n+1)! > (n+1)2^(n+1)
2(n+1)! > 2^(n+1)

This is where I am stuck - I can't figure out how to get rid of that two on the LHS. Any help would be appreciated.

Answer 1

(n+1)!=(n+1)* n!> 2*n! > 2*2^n =2^(n+1)

Where the second > is by induction and the first is because n+1 > 2.

Answer 2

I don't think induction is the best way to prove this. For n>3, n!/2^n = (1 * 2 * 3 * 4 *.....n)/(2 * 2 *.......2) = 6/8 * (4/2) * (5/2)...(n/2) >= 3/4 * 2^(n-3) >= 3/4 * 2 =1.5 > 1, so that n! > 2^n for n > 3

Answer 3

You're right about using induction. However, you're making this a lot harder than it needs to be.

For the induction step: We already know (or assume) that n!>2^n.
We need to show: (n+1)! > 2^(n+1)
But this is the same as saying:
(n+1)*n! > 2*2^n
Given that n!>2^n, and (n+1)>2, the proof should jump right out at you.

I trust that helped. :-)

Answer 4

n!>2^n
n=4
4*3*2*1>2^4 true
let it be true for n=k
k!>2^k
(k+1)!=(k+1)*k! and >2^k+1 as 2^k+1=2*2^k
and k+1>2 as n>3
hence proved