Questions

Prove that (N+1)!/2 = Ω(2^N)

0

Prove the equation using mathematical induction.



asked 1 year, 7 months ago
Reputation: 1





1 Answer

0

To prove:

(N+1)!/2 = Ω(2N)

Proof:

In the induction step, we want to show that if k! ≥ 2k for some k ≥ 4, then (k+1)! ≥ 2k+1.

Since we already know that 4! ≥ 24

The principle of mathematical induction will then allow us to conclude that

n! ≥ 2n 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! ≥ 2k, where k ≥ 4; this is our induction hypothesis.

Then

      (k+1)! = (k+1)k! (by the definition of factorial)
             ≥ (k+1)2k (by the induction hypothesis)
             > 2⋅2k (since k ≥ 4 )
             = 2k+1

This completes the induction step: it shows that if k ≥ 4, then

      k! ≥ 2k

this implies:

      (k+1)! ≥ 2k+1

Similarly,

      (N+1)! ≥ 2N+1

      (N+1)! /2 ≥ 2N

and, hence:

      (N+1)!/2 = Ω(2N)

answered 1 year, 7 months ago
Reputation: 1





Your Answer

Nothing to preview

Post Answer



Asked:  1 year, 7 months ago
Viewed:  376 times
Active:  1 year, 7 months ago