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

  • Thread starter chwala
  • Start date
  • #1
chwala
Gold Member
771
59

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

Answers and Replies

  • #2
chwala
Gold Member
771
59
is my thinking correct? then i can proceed to prove the base, hypothesis then proof of the problem...
 
  • #3
chwala
Gold Member
771
59
1600325449606.png


this is my attempt on the question...are my steps correct?
 
  • #4
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
chwala
Gold Member
771
59
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
chwala
Gold Member
771
59
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
chwala
Gold Member
771
59
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
chwala
Gold Member
771
59
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
chwala
Gold Member
771
59
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
chwala
Gold Member
771
59
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
chwala
Gold Member
771
59
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
chwala
Gold Member
771
59
perok is my language there better, and does my final inequality make sense?
 
  • #18
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
chwala
Gold Member
771
59
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
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
chwala
Gold Member
771
59
wow, looks like some more work....
##2(k+1)^{k+1}≤ (k+2)^{k+1}##
 
  • #22
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
wow, looks like some more work....
##2(k+1)^{k+1}≤ (k+2)^{k+1}##
Hint: binomial theorem.
 
  • #23
chwala
Gold Member
771
59
##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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,732
6,981
##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
chwala
Gold Member
771
59
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
 

Related Threads on Induction maths problem — Using mathematical induction, show that this inequality holds

  • Last Post
Replies
4
Views
978
Replies
4
Views
2K
Replies
2
Views
1K
Replies
10
Views
13K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
7
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
11
Views
2K
Top