# Induction maths problem — Using mathematical induction, show that this inequality holds

Gold Member

## 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}##​

Related Calculus and Beyond Homework Help News on Phys.org
Gold Member
is my thinking correct? then i can proceed to prove the base, hypothesis then proof of the problem...

Gold Member

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

PeroK
Homework Helper
Gold Member
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}$$
$$\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
Gold Member
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}$$
$$\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....

Gold Member
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}$$
$$\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
Homework Helper
Gold Member
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
Homework Helper
Gold Member
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
Gold Member
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
Homework Helper
Gold Member
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.

Gold Member
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.

Gold Member
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...

Last edited:
Gold Member
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
Homework Helper
Gold Member
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
Homework Helper
Gold Member
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.

Gold Member
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...

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

PeroK
Homework Helper
Gold Member
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
Gold Member
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
Homework Helper
Gold Member
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$$

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

PeroK
Homework Helper
Gold Member
wow, looks like some more work....
##2(k+1)^{k+1}≤ (k+2)^{k+1}##
Hint: binomial theorem.

Gold Member
##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+1)^{k+1}≤ (k+2)^{k+1} \Leftrightarrow 2 \le (\frac{k+2}{k+1})^{k+1} = (1 + \frac 1 {k+1})^{k+1}$$