March 6th, 2014, 03:34 AM  #1 
Newbie Joined: Jun 2012 Posts: 9 Thanks: 0  proving big O
so, I have a question that is stated: prove 2^n=O(n!) here is my attempt to prove that the statement is true or false: 2^1=2 1!=1 false 2 is not <= 1 2^2=4 2!=2 false 4 is not <=2 2^3=8 3!=6 false 8 is not <= 6 2^4=16 4!=24 true 16<=24 2^5=32 5!=120 it looks like the statement is true only when n is greater then or equal to 4. am I following this correctly? 
March 6th, 2014, 05:44 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: proving big O
"It looks like" isn't going to help here, since you're asked to prove the inclusion. Here's a thought. Suppose 2^n < n! for some n > 1. Then 2^(n+1) = 2^n * 2 < n! * 2 < n! * (n+1) = (n+1)!. 

Tags 
big, proving 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Need help with proving  rain  Abstract Algebra  4  May 11th, 2013 10:15 AM 
Proving something is a subspace by proving it is a span.  suomik1988  Linear Algebra  1  April 29th, 2011 09:57 PM 
Proving... Help me plz...  isuki  Elementary Math  5  July 27th, 2009 11:55 PM 
proving log(a)  ^e^  Real Analysis  6  March 1st, 2007 08:16 PM 
Proving... Help me plz...  isuki  Number Theory  0  December 31st, 1969 04:00 PM 