Prove: For all n elements of Natural Numbers with n>=4, n!>=n^2 Solution Claim:

Question

Prove: For all n elements of Natural Numbers with n>=4, n!>=n^2

Explanation / Answer

Claim: For all values of n >= 4, n! > n^2. Proof: By induction on n 1) Base case: The statement is claiming a certain relationship between the factorial funcion and the power function for all values greater than four. Since 5 is the next integer it will be the smallest instance of this claim and hence the base case for the proof. Since the statement is claiming a relationship between the factorial and power functions, we must consider both functions when n = 4. Factorial: 4! = 24 Power: 4^2 = 16. Clearly 24 > 16, so the claim is true for the base case. 2) Inductive step: Assume that k! > k^2 is true for some arbitrary value of k > 4. 3) Consider the next problem instance, k + 1. From the definition of the factorial function we know that a) (k + 1)! = (k + 1) * k! From the inductive hypothesis we know that b) k! > k^2 And if k! is larger than k^2 then clearly (k + 1) * k! is larger than (k + 1) * k^2. So: c) (k + 1) * k! > (k + 1) * k^2 And from a) we know that d) (k + 1)! > (k + 1) * k^2 Since k is greater than 3 from the inductive step we know that e) (k + 1) * 2^k > 2 * k^2 Combining d) and e) we finally have: f) (k + 1) * k! > (k + 1) * k^2 > 2 * k^2 and h) (k + 1) * k! > (k + 1)^2 and finally i) (k + 1)! > (k + 1)^2 So, we have proven that the above claim is true for the base case when n = 4. And we have proven that if the claim is true for some arbitrary value, say k, then it is also true for k + 1. HENCE BY PRICIPLE OF MATHEMATICAL INDUCTION => n>=4, n!>=n^2

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.