Proof Question

[Frodo Baggins]

Can anybody find a simple proof showing that n! > 2^n ?

I figured out one proof using Pascal's Triangle, and one using a more visual method, but I'm really searching for a simple proof because I know it exists

[Frodo Baggins]

Oh, just a bump, but I also forgot to mention, don't give me a proof by induction

[WyrmMaster]

well, i can disprove that statement.

what if n=1?

1 != 1
2^1 = 2

[FunkDaMonkMan]

yea well...

1>2
2>4
6>8
24>16....


so you would mean n! > 2^n given that n>3

[Frodo Baggins]

Sorry guys, I wrote the question in a hurry. the original question expected you to find the restriction. yes, n >=4

[David]

Originally posted by Frodo Baggins
Sorry guys, I wrote the question in a hurry. the original question expected you to find the restriction. yes, n >=4

Try Proof by induction:

For n=4, n!=24 n^2=16 so the proof holds for n=4.

Assume n!>n^2 where n=k such that k>=4

We would hope that if k!>k^2 then (k+1)!>(k+1)^2

k!>k^2 assume to be true
k!(k+1)>k^2(K+1)

k!(k+1) = (K+1)!

So

(k+1)! > k^3 + k^2

k^3 + k^2 > k^2 + 2k + 1 for k>=2. In this case k>=4

Thus:

(k+1)! > K^2 + 2K + 1
(k+1)! > (k+1)^2

The statement is true for k+1 if true for k. Thus if true for 4, true for 5. If true for 5, true for 6 etc. Its true for 4, thus true for k>=4.

David

[Frodo Baggins]

David,

Originally posted by Frodo Baggins
Oh, just a bump, but I also forgot to mention, don't give me a proof by induction

I can solve it using Pascal's triangle ( a pretty cheap proof), proof by induction, but I'm looking for a regular number theory proof

Also, it wasn't prove n! > n^2

It was prove n! > 2^n

if your interested, the proof by induction isn't very hard

n! > 2^n

works for n = 4
assume for n = k

prove (k+1)! > 2^(k+1)

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

Remember this is restricted k >= 4

Let it equal the lower bound and the inequality still holds

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

This is obviously true:
(k+1)! >= (2)2^k
(k+1)! >= 2^{k+1} (k is a natural num. k >= 4)

The equality is removed by observing 4! > 2^4

I wanted a regular proof, no induction

[David]

Originally posted by Frodo Baggins
David,



I can solve it using Pascal's triangle ( a pretty cheap proof), proof by induction, but I'm looking for a regular number theory proof

Also, it wasn't prove n! > n^2

It was prove n! > 2^n

if your interested, the proof by induction isn't very hard

n! > 2^n

works for n = 4
assume for n = k

prove (k+1)! > 2^(k+1)

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

Remember this is restricted k >= 4

Let it equal the lower bound and the inequality still holds

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

This is obviously true:
(k+1)! >= (2)2^k
(k+1)! >= 2^{k+1} (k is a natural num. k >= 4)

The equality is removed by observing 4! > 2^4

I wanted a regular proof, no induction

Oops, sorry, misread it a bit...... :eek:

[Frodo Baggins]

Hmmm...

well, I have one proof, don't like it at all though


n! = 1 x 2 x 3 x 4 x 5 x 6 x ...x n
2^n = 2 x 2 x 2 x 2 x 2 x 2 x....x 2


Notice that 1 and 2 are the only ones that don't match

Try it again, but shift it over

n! = 1 x 2 x 3 x 4 x 5 x...x n
2^n = 2 x 2 x 2 x 2 x...x 2 x 2


Chop off that 2 at the end, it's clear that:
n! >= 2^(n-1) for all natural numbers

You can guess that n! > 2^n only for 4 and above, so there must be something with that 4! Well break it up


n! = 1 x 2 x 3 x (2 x 2) x...x n
2^n = 2 x 2 x 2 x 2 x x 2


And there it is, it is clear that:
n! >= 2^n for n >= 4
The equality is removed by noticing n! > 2^n for n = 4