You need to use mathematical induction to prove the formula for every positive integer n, hence, you need to perform the two steps of the method, such that:
Step 1: Basis: Show that the statement P(n) hold for n = 4, such that:
`(4!) => 2^4=> 1*2*3*4 > 16 => 24>16`
Step 2: Inductive step: Show that if P(k) holds, then also P(k + 1) holds:
`P(k): k! > 2^k ` holds
`P(k+1): (k+1)! > 2^(k+1) => k!(k+1) > 2^(k+1)`
You need to use induction hypothesis that P(k) holds, hence, you need to re-write the left side, such that:
`(2^k)(k+1) > 2^(k+1)`
`(2^k)(k+1) > 2*2^k`
`(k+1) > 2*2^k`
Notice that P(k+1) holds.
Hence, since both the basis and the inductive step have been verified, by mathematical induction, the statement `P(n): n! > 2^n ` holds for all positive integers n.
No comments:
Post a Comment