Prove the following by mathematical induction.
2^(n-1)≤n!
P(1), since 2^0 ≤ 1
Now, assume P(k). Then, with n = k+1, we need to show that
2^(k) ≤ (k+1)!
But, we know that
2^k = 2*2^(k-1) ≤ 2*k! ≤ (k+1)*k! ≤ (k+1)! for 2≤k
so, P(k+1) if P(k)
2^(n-1)≤n!
Now, assume P(k). Then, with n = k+1, we need to show that
2^(k) ≤ (k+1)!
But, we know that
2^k = 2*2^(k-1) ≤ 2*k! ≤ (k+1)*k! ≤ (k+1)! for 2≤k
so, P(k+1) if P(k)