Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##

[chwala]

Homework Statement

Using mathematical induction show that
$\sqrt[n]n!$ ≤$\frac{n+1}{2}$ where $n$ lies in $z^+$

Relevant Equations

maths induction

$\sqrt[n]n!$ ≤$\frac{n+1}{2}$​

$\frac {1}{n}$ log [n!]= log$\frac{n+1}{2}$​

 

[chwala]

is my thinking correct? then i can proceed to prove the base, hypothesis then proof of the problem...

 

[chwala]

this is my attempt on the question...are my steps correct?

 

[PeroK]

In both cases you have the implication going in the wrong direction.

What you want to say is that
$$\sqrt[n]n! \le \frac{n+1}{2} \Leftrightarrow \log(\sqrt[n]n!) \le \log(\frac{n+1}{2})$$
And for the inductive step, you have simply written down what you want to show. You simply should never do that. For the inductive step, you either start with:
$$\frac 1 k \log(k!) \le \frac{k+1}{2}$$
And work from there. Or, you start with the expression:
$$\frac 1 {k+1} \log((k+1)!)$$
And work on that until you show that it is less than or equal to $\frac{k+2}{2}$.

Starting with the inequality you are trying to prove is a bad habit that you must break.

PS This one looks quite tricky. I didn't use logs.

 

[chwala]

In both cases you have the implication going in the wrong direction.

What you want to say is that
$$\sqrt[n]n! \le \frac{n+1}{2} \Leftrightarrow \log(\sqrt[n]n!) \le \log(\frac{n+1}{2})$$
And for the inductive step, you have simply written down what you want to show. You simply should never do that. For the inductive step, you either start with:
$$\frac 1 k \log(k!) \le \frac{k+1}{2}$$
And work from there. Or, you start with the expression:
$$\frac 1 {k+1} \log((k+1)!)$$
And work on that until you show that it is less than or equal to $\frac{k+2}{2}$.

Starting with the inequality you are trying to prove is a bad habit that you must break.

PS This one looks quite tricky. I didn't use logs.

how did you solve it without logs...

 

[chwala]

In both cases you have the implication going in the wrong direction.

What you want to say is that
$$\sqrt[n]n! \le \frac{n+1}{2} \Leftrightarrow \log(\sqrt[n]n!) \le \log(\frac{n+1}{2})$$
And for the inductive step, you have simply written down what you want to show. You simply should never do that. For the inductive step, you either start with:
$$\frac 1 k \log(k!) \le \frac{k+1}{2}$$
And work from there. Or, you start with the expression:
$$\frac 1 {k+1} \log((k+1)!)$$
And work on that until you show that it is less than or equal to $\frac{k+2}{2}$.

Starting with the inequality you are trying to prove is a bad habit that you must break.

PS This one looks quite tricky. I didn't use logs.

i do not get , for my inductive step, what you are indicating i do is what i wrote in step 2 of my working...let me get this right when we introduce logs , aren't we supposed to introduce logs on both sides of the inequality? clarify

 

[PeroK]

i do not get , for my inductive step, what you are indicating i do is what i wrote in step 2 of my working...clarify

You started the inductive step with:
$$\frac 1 {k+1} \log(k+1)! \le \log(\frac {k + 1 + 1}{2})$$
But that isn't something you can assume or start with. That is something you have to prove, starting with:
$$\frac 1 {k} \log(k!) \le \log(\frac {k + 1}{2})$$

 

[PeroK]

how did you solve it without logs...

I started by showing that:
$$\sqrt[n]n! \le \frac{n+1}{2} \Leftrightarrow 2^n n! \le (n+1)^n$$
Can you take it from there?

 

[chwala]

You started the inductive step with:
$$\frac 1 {k+1} \log(k+1)! \le \log(\frac {k + 1 + 1}{2})$$
But that isn't something you can assume or start with. That is something you have to prove, starting with:
$$\frac 1 {k} \log(k!) \le \log(\frac {k + 1}{2})$$

my inductive step is indicated as step 2,...in step 3 i was trying to show the proof...i hope i am clear...

 

[PeroK]

my inductive step is indicated as step 2,...in step 3 i was trying to show the proof...i hope i am clear...

What you're doing is not right. If you don't understand what I'm saying then you haven't understood the idea of induction.

 

[chwala]

i agree, i have just seen your hint, pure maths is an area i am trying to study on my own...my area is applied maths...nevertheless i will keep trying to attempt. let me use your hint.

 

[chwala]

am now getting...
1. for base case,
$2^n.n!≤ (n+1)^n$
on putting $n=1$
$2.1≤2$ holds
2. on the inductive step, let $n=k$
$2^k. k!≤(k+1)^k$
3. now on the proof we let $n=k+1$
for lhs, it follows that,
$2^{k+1}. (k+1)!≤ 2^k. 2^1. (k+1).k!$
$≤2. (k+1)^k.(k+1)$
$≤2.(k+1)^{k+1} ≤ (k+2)^{k+1}$ on checking with values of $z^+$ the inequality is satisfied...
am i on the right track boss...

 

[chwala]

i think i just have a problem with the language, i wanted to prove for $n=k+1$ ...instead of saying let $n=k+1$, i have seen the error on my inequality...let me repost down here again...

 

[PeroK]

am now getting...
1. for base case,
$2^n.n!≤ (n+1)^n$
on putting $n=1$
$2.1≤2$ holds
2. on the inductive step, let $n=k$
$2^k. k!≤(k+1)^k$
3. now on the proof we let $n=k+1$
for lhs, it follows that,
$2^{k+1}. (k+1)!≤ 2^k. 2^1. (k+1).k!$
$≤2. (k+1)^k.(k+1)$
$≤2.(k+1)^{k+1} ≤ (k+2)^{k+1}$ on checking with values of $z^+$ the inequality is satisfied...
am i on the right track boss...

Yes, on the right track. But that last step needs some work. For example, you could prove that last inequality by a separate induction.

 

[PeroK]

i think i just have a problem with the language, i wanted to prove for $n=k+1$ ...instead of saying let $n=k+1$, i have seen the error on my inequality...let me repost down here again...

You're getting there, but that last bit is still tricky.

 

[chwala]

am now getting...
1. for base case,
$2^n.n!≤ (n+1)^n$
on putting $n=1$
$2≤2$ holds
2. on the inductive step, let $n=k$
$2^k. k!≤(k+1)^k$
3. now we want to prove if the inequality holds for $n=k+1$
for lhs, it follows that,
$2^{k+1}. (k+1)! = 2^k. 2^1. (k+1).k!$
$=2. (k+1)^k.(k+1)$
$=2.(k+1)^{k+1} ≤ (k+2)^{k+1}$ on checking with values of $z^+$ the inequality is satisfied...
am i on the right track boss...

 

[chwala]

perok is my language there better, and does my final inequality make sense?

 

[PeroK]

perok is my language there better, and does my final inequality make sense?

Yes, but you should prove that last inequality using a separate induction. To help you note that:
$$2(k+1)^{k+1} = 2(\frac{k+1}{k+2})^{k+1} (k+2)^{k+1}$$
If you can show that:
$$\forall k: \ \ 2(\frac{k+1}{k+2})^{k+1} \le 1$$
Then you are done.

 

[chwala]

i can see that, the $(k+2)^{k+1}$ on both sides of the inequality will cancel out and remain with your final inequality...

 

[PeroK]

i can see that, the $(k+2)^{k+1}$ on both sides of the inequality will cancel out and remain with your final inequality...

It's this you have to prove:
$$\forall k: \ \ 2(\frac{k+1}{k+2})^{k+1} \le 1$$

 

[chwala]

wow, looks like some more work...
$2(k+1)^{k+1}≤ (k+2)^{k+1}$

 

[PeroK]

wow, looks like some more work...
$2(k+1)^{k+1}≤ (k+2)^{k+1}$

Hint: binomial theorem.

 

[chwala]

$2[k^{k+1}+ (k+1).k^k+[k.(k+1)^{k-1}]/2+...≤ k^{k+1}+(k+1)k^k. 2+[k(k+1)k^{k-1}.2^2]/2$+...

 

[PeroK]

$2[k^{k+1}+ (k+1).k^k+[k.(k+1)^{k-1}]/2+...≤ k^{k+1}+(k+1)k^k. 2+[k(k+1)k^{k-1}.2^2]/2$+...

What about:
$$2(k+1)^{k+1}≤ (k+2)^{k+1} \Leftrightarrow 2 \le (\frac{k+2}{k+1})^{k+1} = (1 + \frac 1 {k+1})^{k+1}$$

 

[chwala]

Wawawawawawa maths is not for the faint hearted...let me look at this tomorrow, now 10.30pm needto take a nap. Thanks perok we talk tomorrow

 

[chwala]

perok, i am just looking at other examples on induction and there seems not to be a general way of showing the proofs...my question is, (for this particular problem ) is it that we have to prove it using the way you have advised? what is wrong by me using post 16, by substituting directly for $k$ values for $z^+$ and showing that the inequality is satisfied.
can you confirm this other solution posted by my colleague below...

 

[chwala]

is this correct, posted by a colleague...meanwhile i will try and finish on my working from where i had left yesterday...

 

[PeroK]

View attachment 269613

is this correct, posted by a colleague...meanwhile i will try and finish on my working from where i had left yesterday...

What do you think? What part of that solution do you not follow? Do you see anything wrong in the last few steps?

Why don't you check that last line for $k = 1$?

 

[chwala]

What do you think? What part of that solution do you not follow? Do you see anything wrong in the last few steps?

Why don't you check that last line for $k = 1$?

ok just to respond to your question, substituting $k=1$, will yield,
$2^{0.5}≤2^{0.5}≤1≤1.5$ which clearly is not correct...

 

[PeroK]

ok just to respond to your question, substituting $k=1$, will yield,
$2^{0.5}≤2^{0.5}≤1≤1.5$ which clearly is not correct...

Do you see what he did wrong?