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

  • Thread starter chwala
  • Start date
  • Tags
    Proof
In summary: It's important to be precise and clear when writing proofs in mathematics. Using the correct language and notation helps to make your arguments more understandable and convincing. Keep practicing and you will improve your skills in writing mathematical proofs.
  • #1
chwala
Gold Member
2,571
343
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}##​
 
Physics news on Phys.org
  • #2
is my thinking correct? then i can proceed to prove the base, hypothesis then proof of the problem...
 
  • #3
1600325449606.png


this is my attempt on the question...are my steps correct?
 
  • #4
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.
 
  • Like
Likes chwala
  • #5
PeroK said:
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...
 
  • #6
PeroK said:
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
 
  • #7
chwala said:
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})$$
 
  • #8
chwala said:
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?
 
  • Like
Likes chwala
  • #9
PeroK said:
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...
 
  • #10
chwala said:
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.
 
  • #11
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.
 
  • #12
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:
  • #13
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...
 
  • #14
chwala said:
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.
 
  • #15
chwala said:
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.
 
  • #16
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...
 
  • #17
perok is my language there better, and does my final inequality make sense?
 
  • #18
chwala said:
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.
 
  • Like
Likes chwala
  • #19
i can see that, the ##(k+2)^{k+1}## on both sides of the inequality will cancel out and remain with your final inequality...
 
  • #20
chwala said:
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$$
 
  • #21
wow, looks like some more work...
##2(k+1)^{k+1}≤ (k+2)^{k+1}##
 
  • #22
chwala said:
wow, looks like some more work...
##2(k+1)^{k+1}≤ (k+2)^{k+1}##
Hint: binomial theorem.
 
  • #23
##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##+...
 
  • #24
chwala said:
##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}$$
 
  • #25
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
 
  • #26
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...
 
  • #27
1600377290321.png


is this correct, posted by a colleague...meanwhile i will try and finish on my working from where i had left yesterday...
 
  • #28
chwala said:
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##?
 
  • #29
PeroK said:
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...
 
  • #30
chwala said:
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?
 
  • Like
Likes chwala
  • #31
PeroK said:
Do you see what he did wrong?

i see that the inequality is not correct, i want to take my time today to analyse the remaining bit of my working and also to look at his working, step by step...lets talk in the course of the day...
 
  • #32
my friend managed to re check his working on the problem and i can follow through his steps with ease kindly see attached below;
 
  • #33
1600516802796.png
 
  • #34
now let me continue with where i left...give me some moment...
 
  • #35
chwala said:
my friend managed to re check his working on the problem and i can follow through his steps with ease kindly see attached below;
He still needs to justify that last step.
 
<h2>1. What is the significance of the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##"?</h2><p>This inequality is significant because it provides a bound for the value of ##\sqrt[n]{n!}##, which is the nth root of n factorial. It shows that this value is always less than or equal to ##\frac{n+1}{2}##, which can be useful in various mathematical proofs and calculations.</p><h2>2. How is the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##" proven?</h2><p>The inequality can be proven using mathematical induction. The base case, n=1, is trivial. For the inductive step, assume the inequality holds for some value k. Then, for k+1, we have ##\sqrt[k+1]{(k+1)!}## = ##\sqrt[k]{k!}## * ##\sqrt[k+1]{k+1}## ≤ ##\frac{k+1}{2}## * ##\sqrt[k+1]{k+1}##. By the inductive hypothesis, ##\sqrt[k]{k!}## ≤ ##\frac{k+1}{2}##, so we have ##\sqrt[k+1]{(k+1)!}## ≤ ##\frac{k+1}{2}## * ##\sqrt[k+1]{k+1}## = ##\frac{(k+1)(k+1)}{2}## = ##\frac{(k+1)+1}{2}##, completing the induction. </p><h2>3. What is the relationship between ##\sqrt[n]{n!}## and ##\frac{n+1}{2}##?</h2><p>The relationship between ##\sqrt[n]{n!}## and ##\frac{n+1}{2}## is that the former is always less than or equal to the latter. This means that ##\sqrt[n]{n!}## is always bounded by ##\frac{n+1}{2}##, and the difference between the two values decreases as n increases.</p><h2>4. Can the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##" be generalized to other values besides n?</h2><p>Yes, the inequality can be generalized to other values besides n. For example, it can be shown that for any positive integer k, ##\sqrt[k]{k!}## ≤ ##\frac{k+1}{2}##. This can be proven using a similar induction argument as in question 2.</p><h2>5. How is the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##" used in practical applications?</h2><p>The inequality can be used in various mathematical calculations and proofs, such as in the analysis of algorithms or in probability theory. It can also be used as a tool for approximating values, as the value of ##\frac{n+1}{2}## is often easier to calculate than ##\sqrt[n]{n!}##. Additionally, the inequality can be used to prove other more complex inequalities and theorems.</p>

1. What is the significance of the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##"?

This inequality is significant because it provides a bound for the value of ##\sqrt[n]{n!}##, which is the nth root of n factorial. It shows that this value is always less than or equal to ##\frac{n+1}{2}##, which can be useful in various mathematical proofs and calculations.

2. How is the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##" proven?

The inequality can be proven using mathematical induction. The base case, n=1, is trivial. For the inductive step, assume the inequality holds for some value k. Then, for k+1, we have ##\sqrt[k+1]{(k+1)!}## = ##\sqrt[k]{k!}## * ##\sqrt[k+1]{k+1}## ≤ ##\frac{k+1}{2}## * ##\sqrt[k+1]{k+1}##. By the inductive hypothesis, ##\sqrt[k]{k!}## ≤ ##\frac{k+1}{2}##, so we have ##\sqrt[k+1]{(k+1)!}## ≤ ##\frac{k+1}{2}## * ##\sqrt[k+1]{k+1}## = ##\frac{(k+1)(k+1)}{2}## = ##\frac{(k+1)+1}{2}##, completing the induction.

3. What is the relationship between ##\sqrt[n]{n!}## and ##\frac{n+1}{2}##?

The relationship between ##\sqrt[n]{n!}## and ##\frac{n+1}{2}## is that the former is always less than or equal to the latter. This means that ##\sqrt[n]{n!}## is always bounded by ##\frac{n+1}{2}##, and the difference between the two values decreases as n increases.

4. Can the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##" be generalized to other values besides n?

Yes, the inequality can be generalized to other values besides n. For example, it can be shown that for any positive integer k, ##\sqrt[k]{k!}## ≤ ##\frac{k+1}{2}##. This can be proven using a similar induction argument as in question 2.

5. How is the inequality "Proof of ##\sqrt[n]{n!}## ≤ ##\frac{n+1}{2}##" used in practical applications?

The inequality can be used in various mathematical calculations and proofs, such as in the analysis of algorithms or in probability theory. It can also be used as a tool for approximating values, as the value of ##\frac{n+1}{2}## is often easier to calculate than ##\sqrt[n]{n!}##. Additionally, the inequality can be used to prove other more complex inequalities and theorems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
397
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
182
  • Calculus and Beyond Homework Help
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Calculus and Beyond Homework Help
Replies
13
Views
627
  • Calculus and Beyond Homework Help
Replies
1
Views
434
  • Calculus and Beyond Homework Help
Replies
15
Views
974
Back
Top