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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search