1. ## More induction help

Can someone give me a hint as to where to start while attempting this problem?

Use mathematical induction to prove that n!<n^n whenever n is a positive integer greater than 1.

2. This is what I have so far...

Basis step: P(2) states that 2! is less than 2^2. This is true since 2! = 2 and 2^2=4 and 2<4.

Inductive step: Assume n is greater than 1. Assume P(n) is true: that is
n! < n^n

This is where I am stuck!

3. Originally Posted by sjenkins
This is what I have so far...

Basis step: P(2) states that 2! is less than 2^2. This is true since 2! = 2 and 2^2=4 and 2<4.

Inductive step: Assume n is greater than 1. Assume P(n) is true: that is
n! < n^n

This is where I am stuck!
Multiply both sides of:

$n!

by $n+1$ to get:

$(n+1) \times n!=(n+1)! < (n+1) \times n^n$

So:

$(n+1)!

Now taking the first two terms of the binomial expansion of $(n+1)^{n+1}$ we get:

$(n+1)^{n+1}=n^{n+1}+(n+1)n^n+R$

where $R>0$ is the remainder (which is greater than zero because all of the terms left out of this are also positive).

So:

$(n+1)^{n+1}=n^{n+1}+n^n+n^{n+1}+R$

Hence:

$(n+1)^{n+1}>n^{n+1}+n^n$

and so going back to $(1)$ we have:

$(n+1)!

which completes the proof of the induction step.

RonL

4. [quote=CaptainBlack;164709]Multiply both sides of:

$n!

by $n+1$ to get:

$(n+1) \times n!=(n+1)! < (n+1) \times n^n$

So:

$(n+1)!

Now taking the first two terms of the binomial expansion of $(n+1)^{n+1}$ we get:

$(n+1)^{n+1}=n^{n+1}+(n+1)n^n+R$

Can you please explain how to factor these, I don't understand how, for example (n+1)Xn^n becomes n^n+1+n^n. I also am not understanding the part where it says taking the first two terms of the binomail expansion... where did that come from?

I'm sorry to sound so crazy, I just am not grasping this quite yet!

5. Originally Posted by sjenkins
Originally Posted by CaptainBlack
Multiply both sides of:

$n!

by $n+1$ to get:

$(n+1) \times n!=(n+1)! < (n+1) \times n^n$

So:

$(n+1)!

Now taking the first two terms of the binomial expansion of $(n+1)^{n+1}$ we get:

$(n+1)^{n+1}=n^{n+1}+(n+1)n^n+R$

Can you please explain how to factor these, I don't understand how, for example (n+1)Xn^n becomes n^n+1+n^n. I also am not understanding the part where it says taking the first two terms of the binomail expansion... where did that come from?

I'm sorry to sound so crazy, I just am not grasping this quite yet!
Multiply out the bracket:

$(n+1) n^n= n \times n^n +n^n$

Now by the rules of indices:

$n \times n^n=n^{n+1},$

so:

$(n+1) n^n= n \times n^n +n^n=n^{n+1}+n^n$

RonL

6. Originally Posted by sjenkins
Originally Posted by CaptainBlack
Multiply both sides of:

$n!

by $n+1$ to get:

$(n+1) \times n!=(n+1)! < (n+1) \times n^n$

So:

$(n+1)!

Now taking the first two terms of the binomial expansion of $(n+1)^{n+1}$ we get:

$(n+1)^{n+1}=n^{n+1}+(n+1)n^n+R$

Can you please explain how to factor these, I don't understand how, for example (n+1)Xn^n becomes n^n+1+n^n. I also am not understanding the part where it says taking the first two terms of the binomail expansion... where did that come from?

I'm sorry to sound so crazy, I just am not grasping this quite yet!
You should know the binomial theorem:

$(a+b)^k=a^k + k a^{k-1}b + .. +
\left( {\begin{array}{*{20}c}
k \\
r \\
\end{array}} \right)a^{k-r}b^r + .. +kab^{k-1}+b^k
$

So apply this to $(n+1)^{n+1}$ with $a=n$, $b=1$ and $k=n+1$ to get:

$
(n+1)^{n+1}=n^{k+1}+(n+1)n^k + \text{ and other terms all positive}
$

RonL