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:

$\displaystyle n!<n^n$

by $\displaystyle n+1$ to get:

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

So:

$\displaystyle (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)$

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

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

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

So:

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

Hence:

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

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

$\displaystyle (n+1)!<n^{n+1}+n^n<(n+1)^{n+1}$

which completes the proof of the induction step.

RonL

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

$\displaystyle n!<n^n$

by $\displaystyle n+1$ to get:

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

So:

$\displaystyle (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)$

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

$\displaystyle (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:

$\displaystyle n!<n^n$

by $\displaystyle n+1$ to get:

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

So:

$\displaystyle (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)$

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

$\displaystyle (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:

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

Now by the rules of indices:

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

so:

$\displaystyle (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:

$\displaystyle n!<n^n$

by $\displaystyle n+1$ to get:

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

So:

$\displaystyle (n+1)!<n^{n+1}+n^n \ \ \ \ \ \ \ ...(1)$

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

$\displaystyle (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:

$\displaystyle (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 $\displaystyle (n+1)^{n+1}$ with $\displaystyle a=n$, $\displaystyle b=1$ and $\displaystyle k=n+1$ to get:

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

RonL