# Mathematical Induction trouble with 1 step!

1. Jan 21, 2006

### forevergone

Hi there folks, I have just a small problem with a specific induction problem. The problem itself is: "Prove $$n! > 4^n$$, for all n >= 9."

So here's my work:

1) Show true for n = 9
LS
9! = 362880

RS
4^9 = 262144

.:. LS > RS

2) Assume true for n = k
i.e. Assume that k! > 4^k

3) Prove true for n = k+1
i.e. Prove that (k+1)! > 4^(k+1)

So I begin to expand the LHS out

(k+1)! = (k+1)(k)!
> (K+1)(4^k) (by induction hypothesis)

this is the problem that I encounter. I get stuck here because I don't exactly know how to followthrough at this point. How does (k+1)(4^k) become greater that 4^(k+1) ?

2. Jan 21, 2006

### VietDao29

If k >= 9, then what can you say about k + 1? How is k + 1 compared to 4 (greater, less than, or equal to)?
So from there can you prove that (k + 1)4k > 4k + 1 = 4 4k?

3. Jan 22, 2006

### forevergone

OH. I see, since k always going to be at least 10. I didn't see it that way.

Dammit! Oh well, a few silly mistakes cost me quite alot.

Thanks.

Last edited: Jan 22, 2006