See the attach file for problem. Please read R as R+
Question :
Prove that ! ( )
n
n ∈ο n by using the definition of the small o- notation.
Definition: Let : N →R∪{0}, where
∫
N is the set of all non-negative integers:
R is the set of all positive real numbers.
f
0 0
o( f )={ g : N →R ∪{0}|∀c∈R,∃n ∈N :g(n) Solution
The factorial of n, represented by n! is defined for integers n ≥ 0 as
n! = 1 if n=0
= n. (n-1)! if n>0
First of all let us try and arrive at an intuitive solution. A weak upper bound on n! is n
n
, since
each of the n terms in the factorial product is at most n. The o-notation is used to denote an upper
bound that is NOT asymptotically tight.
Hence, intuitively ! ( )
n
n ∈ο n
Proof:
To prove this we need to prove that the definition of o-notation holds.
According to the definition of o-notation, we need to prove that for any positive constant c > 0, there exists a constant n0 >0 such that
0 ≤ n! < c n
n
for all n ≥ n0 Equation (i)
So it now boils down to showing that the inequalities hold and then we are done.
(a) The first inequality (0 ≤ n!) follows from the definition of n! :
• n! is always greater than 0.
• Minimum value of n! is 1 which occurs when n=0.
Hence n! ≥ 0 for all n ≥ 0.
(b) To show the second inequality, we just need to look at the factorials carefully.
Once again, let us start with the basic factorials: 0! = 1 and 1! = 1. So in order for these factorials
to satisfy the inequality, it is obvious that c must be >1 [because 1 < c*1 iff c >1].
For all other factorials, i.e. n ≥ 2, the inequality will hold for any c > 1. So, in order to
summarize:
The second inequality n! < c n
n
is true for n ≥ 2 for any c ≥1. This is in the same form as
Equation (i).
Therefore for all c ε R+, n0 = 2 satisfies Equation (i).
Hence ! ( )
n
n ∈ο n is proved