Proof by Induction
Date: 05/07/2003 at 04:04:21 From: Sarah Subject: Proof by Induction Use induction to prove: If n >= 6 then n! >= n(2^n) This is unlike all other induction problems. I get lost when I do the induction step. Base case: 6! >= 6(2^6) 720 >= 384 Induction Step: (n + 1)! >= (n + 1) (2^(n + 1)) n! >= n*2^n
Date: 05/07/2003 at 05:50:13 From: Doctor Luis Subject: Re: Proof by Induction Hi Sarah, Good work establishing the base case and the induction step. I'll start you up by showing you writing down my thoughts on how I would solve this problem. If at any point while reading this, you see the solution, stop and work it out on your own, and then come back and keep reading. Given n! >= n(2^n), we have to figure out a way to make that look like (n + 1)! >= (n + 1)(2^(n + 1)). The first thing we see is that (n + 1)! = (n + 1) * n!, and this is >= n * n!, which gives us the n! for which we made the assumption. This suggests the following: n! >= n * (2^n) (start from assumption) n * n! >= n * n * (2^n) (multiply by n) (n + 1)! >= n * (n * 2^n) = n^2 * 2^n Now we're getting somewhere, but there's an extra n on the right side. Maybe we can do something with the inequality n >= 6. n >= 6 n^2 >= 6n = 2 * (3n) = 2 * (n + n + n) Hmm. That 2 may come in useful in getting us from 2^n to 2^(n + 1). Now, how does n + 1 compare with n + n + n? Eureka! n + n + n >= n + 1. You can see this from n >= 6, 2n >= 12 + 1, 3n > 1 + n. Combining all these inequalities, you can prove the induction step. - Doctor Luis, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.