Induction help

pikminman · #1 $Old$ November 16th, 2009, 09:53 AM

Hi I have an induction question. I think I have the thing done properly, I'm just not 100% sure.

The question is: prove that (3n)! <= 27^n (n!)^3
for all positive integers n.

This is what I have so far:

show for 1:
6<27

assume true for k where k is some positive integer
(3k)! <= 27^k (k!)^3

prove true for k+1
(3(k+1))! <= 27^(k+1) (k+1!)^3
(3k + 3)! <= (27^k)(27)((k!)^3)((k+1)^3)
((3k)!)(3k+1)(3k+2)(3k+3) <= (27^k)(27)((k!)^3)((k+1)^3)
THIS IS THE STEP I'M UNSURE ABOUT!!
I take out the original equation.. is this ok?
(3k+1)(3k+2)(3k+3) <= (27)(k+1)^3
27k^3 + 54k^2 + 33k + 6 <= 27k^3 + 81m^2 + 81m + 27

QED?

Drexel28 · #2 $Old$ November 16th, 2009, 10:09 AM

Quote:

Originally Posted by pikminman $View Post$

Hi I have an induction question. I think I have the thing done properly, I'm just not 100% sure.

The question is: prove that (3n)! <= 27^n (n!)^3
for all positive integers n.

This is what I have so far:

show for 1:
6<27

assume true for k where k is some positive integer
(3k)! <= 27^k (k!)^3

prove true for k+1
(3(k+1))! <= 27^(k+1) (k+1!)^3
(3k + 3)! <= (27^k)(27)((k!)^3)((k+1)^3)
((3k)!)(3k+1)(3k+2)(3k+3) <= (27^k)(27)((k!)^3)((k+1)^3)
THIS IS THE STEP I'M UNSURE ABOUT!!
I take out the original equation.. is this ok?
(3k+1)(3k+2)(3k+3) <= (27)(k+1)^3
27k^3 + 54k^2 + 33k + 6 <= 27k^3 + 81m^2 + 81m + 27

QED?

Note that $\lim_{n\to\infty}\frac{27(n+1)!^3}{(3n+3)!}\cdot\frac{(3n)!}{27n!^3}=\frac{1}{27}$ . This means that $\frac{27(n!)^3}{(3n)!}\to0$ so clearly at some point $(3n)!>27(n!)^3$ . Maybe you want to relook at the question.

pikminman · #3 $Old$ November 16th, 2009, 10:12 AM

Quote:

Originally Posted by Drexel28 $View Post$

Note that $\lim_{n\to\infty}\frac{27(n+1)!^3}{(3n+3)!}\cdot\frac{(3n)!}{27n!^3}=\frac{1}{27}$ . This means that $\frac{27(n!)^3}{(3n)!}\to0$ so clearly at some point $(3n)!>27(n!)^3$ . Maybe you want to relook at the question.

I said 27^n not just 27. Maybe I don't understand what you mean.