- #1
forevergone
- 49
- 0
Hi there folks, I have just a small problem with a specific induction problem. The problem itself is: "Prove [tex]n! > 4^n[/tex], 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) ?
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) ?