Please show me by math induction. n factorial less than or equal to 2^(n-1).
Thank you,
Thank you,
-
You might have mistyped “<=.” The inequality you mentioned should be
n!≥2^(n-1) for all n in N. …(*)
Proof of (*): We will prove it by induction.
Basis Case: The case n=1 : (*) is obviously true.
Inductive Step: We assume (*) is true for n=k (k≥1). We then have
k!≥2^(k-1).
Multiplying both sides by k+1(≥2), we have
(k+1)*k!≥(k+1)*2^(k-1).
Since k+1≥2,
(k+1)*k!≥(k+1)*2^(k-1)≥2*2^(k-1).
Hence, we have (k+1)!≥2^((k+1)-1).
It means (*) is true for n=k+1.
We complete our induction, and have shown that (*) is true.
n!≥2^(n-1) for all n in N. …(*)
Proof of (*): We will prove it by induction.
Basis Case: The case n=1 : (*) is obviously true.
Inductive Step: We assume (*) is true for n=k (k≥1). We then have
k!≥2^(k-1).
Multiplying both sides by k+1(≥2), we have
(k+1)*k!≥(k+1)*2^(k-1).
Since k+1≥2,
(k+1)*k!≥(k+1)*2^(k-1)≥2*2^(k-1).
Hence, we have (k+1)!≥2^((k+1)-1).
It means (*) is true for n=k+1.
We complete our induction, and have shown that (*) is true.