To prove:
(N+1)!/2 = Ω(2^{N})
Proof:
In the induction step, we want to show that if k! ≥ 2^{k} for some k ≥ 4, then (k+1)! ≥ 2^{k+1}.
Since we already know that 4! ≥ 2^{4}
The principle of mathematical induction will then allow us to conclude that
n! ≥ 2^{n} for all n ≥ 4.
We have all of the necessary pieces; we just need to put them together properly. Specifically, we can argue as follows.
Suppose that k! ≥ 2^{k}, where k ≥ 4; this is our induction hypothesis
.
Then
(k+1)! = (k+1)k! (by the definition of factorial)
≥ (k+1)2^{k} (by the induction hypothesis)
> 2⋅2^{k} (since k ≥ 4 )
= 2^{k+1}
This completes the induction step: it shows that if k ≥ 4, then
k! ≥ 2^{k}
this implies:
(k+1)! ≥ 2^{k+1}
Similarly,
(N+1)! ≥ 2^{N+1}
(N+1)! /2 ≥ 2^{N}
and, hence:
(N+1)!/2 = Ω(2^{N})