Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/