Help with difficult mathematical induction exercise

[PabloPad]

I would like to know how to prove the following statement by the principle of mathematical induction, it is the last exercise of the Mathematical Induction chapter of the Haese HL Math 3rd edition book:

 

"The nth root of n! is less or equal to (n+1)/2, given any possitive integer n"

 

Edited July 5, 2014 by PabloPad

[Rahul]

Please see the below images for my solution! Thank you for the question, it was quite tricky. Please let me know if I can explain anything I did further for you.

 

[PabloPad]

Please see the below images for my solution! Thank you for the question, it was quite tricky. Please let me know if I can explain anything I did further for you.

 

 

Thanks a lot! But I'm still not sure that the last argument is valid, and here's what I mean:

 

You say that we can use the reverse of the proof to demonstrate the implication P(k) -> P(k+1), but how in fact can you develop such a reverse proof? 

 

2^(1/n)*n!^(1/n) less or equal to (n+1)/2 indeed implies that n!^(1/n) is less or equal to (n+1)/2;

however, n!^(1/n) less or equal to (n+1)/2 does not imply that 2^(1/n)*n!^(1/n) is less or equal to (n+1)/2, since multiplying the LHS times 2^(1/n) makes it greater, and thus the transitivity does not follow.

 

Can you explain me this reasoning? Thanks again! 

Edited July 6, 2014 by PabloPad

[Rahul]

 

Please see the below images for my solution! Thank you for the question, it was quite tricky. Please let me know if I can explain anything I did further for you.

 

 

Thanks a lot! But I'm still not sure that the last argument is valid, and here's what I mean:

 

You say that we can use the reverse of the proof to demonstrate the implication P(k) -> P(k+1), but how in fact can you develop such a reverse proof? 

 

2^(1/2)*n^(1/2) less or equal to (n+1)/2 indeed implies that n^(1/2) is less or equal to (n+1)/2;

however, n^(1/2) less or equal to (n+1)/2 does not imply that 2^(1/2)*n^(1/2) is less or equal to (n+1)/2, since multiplying the LHS times 2^(1/2) makes it greater, and thus the transitivity does not follow.

 

Can you explain me this reasoning? Thanks again! 

 

 

You're very right, actually, and I didn't catch that when I made that (false) assertion - that's one downside of using these inequality tricks, as that means we can't run through the proof 'backwards' whereas without these statements we could. I'll see if I can come up with an alternative proof, or one that is more sound.

[Rahul]

Okay, got it. That was quite a bit more complex than the original proof, and induction had to be used to prove another inequality within this proof! There were a few sections here where I stated S(k) but used n of k in the statement. Please disregard that and any other similar mistakes.

 

 

Let me know if I've made any mistakes in this or can explain any of my steps in this better. Hope this helps!

[PabloPad]

Okay, got it. That was quite a bit more complex than the original proof, and induction had to be used to prove another inequality within this proof! There were a few sections here where I stated S(k) but used n of k in the statement. Please disregard that and any other similar mistakes.

 

Let me know if I've made any mistakes in this or can explain any of my steps in this better. Hope this helps!

 

 

I've found a mistake actually. In the secondary proof T(n), when you rearrange the parenthesis of the LHS by adding and subtracting 1/(n+2), you mistakenly change the sign of 1/(n+1), which was positive in the previous step. By correcting this mistake, the transitivity does not follow

 

This looks a lot like most of my attempts to prove the proposition, in all of them I've got to the point in which I have to include another induction within the first. I believe this is the way to do it, but it sometimes feels like I'm walking in circles. It's quite tricky.

[Andy Sebastian]

I just spent a lot of time trying to do the proof an unconventional, possibly not inductive way, but proving it for the case n = 1, taking the derivative of both sides (substituting the gamma function for n!), and then attempting to demonstrate that as (n+1)/2 = (n!)^(1/n) at n = 1, and d/dn of the latter is greater than or equal to d/dn of the former for all n >= 2, therefore the proposition must be true, but the equation was far too complicated for me to solve.

 

graphing the two into wolfram alpha: http://www.wolframalpha.com/input/?i=%28gamma+function+%28n%29%29^%281%2Fn%29+%3D+%28n%2B1%29%2F2

 

There is only one solution at n = 1.  This isn't at all the type of inductive proof you are looking for, but...could this appraoch have potential with some more competent computation?

 

You can find the derivative of the original function (n!)^(1/n): (n!)^(1/n)[-n^(-2)ln(gamma)+1/(n * gamma) * d gamma / d n, where gamma is the integral from 0 to infinity of e^-t * t^(x-1) dt, and d n /d gamma = gamma(-C - 1/x + summation from b=1 to infinity of x/(b(x+b)), where x = n-1 and C is euler's constant.  This should never exceed the derivative of (n+1)/2, or else any excession would be transient and/or converging to a finite integral less than that of the difference that already exists bew-

 

Yeah, I'm just thinking aloud.  This idea doesn't work, lol.

[Rahul]

 

Okay, got it. That was quite a bit more complex than the original proof, and induction had to be used to prove another inequality within this proof! There were a few sections here where I stated S(k) but used n of k in the statement. Please disregard that and any other similar mistakes.

 

Let me know if I've made any mistakes in this or can explain any of my steps in this better. Hope this helps!

 

 

I've found a mistake actually. In the secondary proof T(n), when you rearrange the parenthesis of the LHS by adding and subtracting 1/(n+2), you mistakenly change the sign of 1/(n+1), which was positive in the previous step. By correcting this mistake, the transitivity does not follow

 

This looks a lot like most of my attempts to prove the proposition, in all of them I've got to the point in which I have to include another induction within the first. I believe this is the way to do it, but it sometimes feels like I'm walking in circles. It's quite tricky.

 

 

Darn, not sure how I made that mistake! Glad you caught it though. 

 

Hmm. If you take a look at the proof I crossed out, you can see me attempting to take derivatives to show that the LHS of T(n) is always increasing for n > 1 - in addition, that in combination with the fact that LHS(1)=2.25 would be sufficient to show T(n) and hence S(n). I didn't have any luck with that, though. I'll give it another attempt - perhaps that approach is what is needed for T(n).

 

In any case, this is certainly beyond anything we'd see on an exam!

[ctrls]

I've been eyeing this problen since yesterday, but I can't seem to make much progress on it either. The question seems waaay to difficult to appear in a HL maths textbook, either I'm missing something or they didn't realize how hard it was.

So far I've reached the result that if the inequality holds for all positive n, then the original inequality is true. I can't type up my working because I'm on my phone, but a quick check with wolframalpha seems to suggest the inequality is true - except I can't seem to prove it. I'll try again tommorow and will post again if I make any further progress.

[PabloPad]

I've been eyeing this problen since yesterday, but I can't seem to make much progress on it either. The question seems waaay to difficult to appear in a HL maths textbook, either I'm missing something or they didn't realize how hard it was.

So far I've reached the result that if the inequality holds for all positive n, then the original inequality is true. I can't type up my working because I'm on my phone, but a quick check with wolframalpha seems to suggest the inequality is true - except I can't seem to prove it. I'll try again tommorow and will post again if I make any further progress.

I've got to that same point! And the inequality is in fact true, but I just can't prove it algebraically.

[ctrls]

Ok, this is starting to bother me now - I still can't prove it! (By induction, anyway) I've reduced the problem further, but I'm not sure if I'm on the right track.

By taking logs on both sides of the previous result, moving all the terms to the right and differentiating the result, I reduced the inequality to . I know I'm being rather vauge with my explanation, but I'll try post a proper solution if I manage to solve it. Anyway, this has me a bit hopeful because it loosely resembles the definition of e. It doesn't seem to help though, so I'm still not really sure.

On a side nor, this inequality is fairly straightforeward to prove if you assume Stirling's approximation, which states that . I believe the proof of this inequality is doable with HL maths knowledge (I remember doing a STEP question of deriving it), so it's not completely impossible to prove it. Now that I think about it, perhaps the above inequality may be provable by induction too (though I haven't tried it).

Edit: If you did the calculus option and know about approximating integrals by summations, then you can prove the above inequality by considering the integral of ln(x). It doesn't help with proving the initial inequality by induction, but it thought it was interesting.

Edited July 8, 2014 by ctrls

[Rahul]

Ok, this is starting to bother me now - I still can't prove it! (By induction, anyway) I've reduced the problem further, but I'm not sure if I'm on the right track.

By taking logs on both sides of the previous result, moving all the terms to the right and differentiating the result, I reduced the inequality to . I know I'm being rather vauge with my explanation, but I'll try post a proper solution if I manage to solve it. Anyway, this has me a bit hopeful because it loosely resembles the definition of e. It doesn't seem to help though, so I'm still not really sure.

On a side nor, this inequality is fairly straightforeward to prove if you assume Stirling's approximation, which states that . I believe the proof of this inequality is doable with HL maths knowledge (I remember doing a STEP question of deriving it), so it's not completely impossible to prove it. Now that I think about it, perhaps the above inequality may be provable by induction too (though I haven't tried it).

Edit: If you did the calculus option and know about approximating integrals by summations, then you can prove the above inequality by considering the integral of ln(x). It doesn't help with proving the initial inequality by induction, but it thought it was interesting.

 

Got the same inequality at one point! You could certainly do it via approximations, but I keep thinking there's got to be an easier way to resolve these things. Perhaps not, though - they certainly couldn't give us something like this on an exam, and for that I am thankful.

[PabloPad]

 

Ok, this is starting to bother me now - I still can't prove it! (By induction, anyway) I've reduced the problem further, but I'm not sure if I'm on the right track.

By taking logs on both sides of the previous result, moving all the terms to the right and differentiating the result, I reduced the inequality to . I know I'm being rather vauge with my explanation, but I'll try post a proper solution if I manage to solve it. Anyway, this has me a bit hopeful because it loosely resembles the definition of e. It doesn't seem to help though, so I'm still not really sure.

On a side nor, this inequality is fairly straightforeward to prove if you assume Stirling's approximation, which states that . I believe the proof of this inequality is doable with HL maths knowledge (I remember doing a STEP question of deriving it), so it's not completely impossible to prove it. Now that I think about it, perhaps the above inequality may be provable by induction too (though I haven't tried it).

Edit: If you did the calculus option and know about approximating integrals by summations, then you can prove the above inequality by considering the integral of ln(x). It doesn't help with proving the initial inequality by induction, but it thought it was interesting.

 

Got the same inequality at one point! You could certainly do it via approximations, but I keep thinking there's got to be an easier way to resolve these things. Perhaps not, though - they certainly couldn't give us something like this on an exam, and for that I am thankful.

 

I've been investigating a while and I found that the way to prove the inequality is through the proof of the inequality between the arithmetic and geometric means for any set of numbers, which can be actually done by induction, though the method is a bit more complex than the cases we've seen. In this link you can check the proof: http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means

From that proof, it follows that:

 

 

Edited July 9, 2014 by PabloPad

[Rahul]

 

 

Ok, this is starting to bother me now - I still can't prove it! (By induction, anyway) I've reduced the problem further, but I'm not sure if I'm on the right track.

By taking logs on both sides of the previous result, moving all the terms to the right and differentiating the result, I reduced the inequality to . I know I'm being rather vauge with my explanation, but I'll try post a proper solution if I manage to solve it. Anyway, this has me a bit hopeful because it loosely resembles the definition of e. It doesn't seem to help though, so I'm still not really sure.

On a side nor, this inequality is fairly straightforeward to prove if you assume Stirling's approximation, which states that . I believe the proof of this inequality is doable with HL maths knowledge (I remember doing a STEP question of deriving it), so it's not completely impossible to prove it. Now that I think about it, perhaps the above inequality may be provable by induction too (though I haven't tried it).

Edit: If you did the calculus option and know about approximating integrals by summations, then you can prove the above inequality by considering the integral of ln(x). It doesn't help with proving the initial inequality by induction, but it thought it was interesting.

 

Got the same inequality at one point! You could certainly do it via approximations, but I keep thinking there's got to be an easier way to resolve these things. Perhaps not, though - they certainly couldn't give us something like this on an exam, and for that I am thankful.

 

I've been investigating a while and I found that the way to proof the inequality is through the proof of the inequality of the arithmetic and geometric means of any set of numbers, which can be actually done by induction, though the method is a bit more complex than the cases we've seen. In this link you can check the proof: http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means

From that proof, it follows that:

 

 

Oh! And the arithmetic mean is always greater than or equal to the geometric mean. That's incredible.

[ctrls]

I've been investigating a while and I found that the way to prove the inequality is through the proof of the inequality between the arithmetic and geometric means for any set of numbers, which can be actually done by induction, though the method is a bit more complex than the cases we've seen. In this link you can check the proof: http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means

From that proof, it follows that:

Wow, that didn't occur to me at all. That's a really neat result, it simplifies so nicely!

I%m going to try prove AM-GM now, just for the sake of completeness. I'm curious if it gives any insight to proving the inequality using a standard induction method. (Doing maths post IB and STEP is so much fun, I can just pick interesting topics and try stuff )

[Guest SNJERIN]

I Don't understand why you guys making the problem seem so complicated !

Its the same as any other induction problem.

1) true for p(1)

--> (1!)^1 ≤ (1+1)/2 which is true! 

Now assuming the statement is true for some values of k such that k € n 

so :- p(k) which is (k!)^1/k ≤ (k+1)/2

if we multiply each side by the reciprocal exponent we get : 

k! ≤ ((k+1)/2)^k which is still true ( since we already assumed it is) 

now we prove for n= k+1 

so :- (k+1)! ≤ ((k+2)/2)^(k+1)

       (k+1)k! ≤   ((k+2)/2)^(k+1)

but since  

k! ≤ ((k+1)/2)^k

now if we multiply (k+1) with both sides we get 

(k+1)k! ≤ ((k+1)/2)^k(k+1)= ((k+1)/2)^(k+1) 

 

 if (k+1)k! ≤ ((k+1)/2)^(k+1) 

then its also < ((k+2)/2)^(k+1)

 

so we get this :-

 

(k+1)! ≤ ((k+1)/2)^(k+1) < ((k+2)/2)^(k+1) for all values of k such that k € n€ Z

Edited August 7, 2014 by Haitham Wahid

[ctrls]

(k+1)k! ≤ ((k+1)/2)^k(k+1)= ((k+1)/2)^(k+1)

This line is incorrect, unfortunately. . I think I got to the same point when I tried it using the standard approach, but I couldn't get much further from here.

I'm impressed at how well you argued this though, considering you're a May 2016 student. Induction aside, proving inequalities properly isn't easy so kudos to you.

[Guest SNJERIN]

OH man, what a terrible mistake!!!

however, have a look at this..

[ctrls]

OH man, what a terrible mistake!!!

however, have a look at this..

You're close, I think it is possible to prove it the way you have. You've missed something though, you haven't proved that the inequality holds for all n, rather you proved that it does when n tends to infinity. The inequality is true though and I'm pretty sure it can be proved fairly easily using calculus methods (show it has no stationary point in the domain (0,infinity)).

Edited August 8, 2014 by ctrls

[Guest SNJERIN]

 

OH man, what a terrible mistake!!!

however, have a look at this..

You're close, I think it is possible to prove it the way you have. You've missed something though, you haven't proved that the inequality holds for all n, rather you proved that it does when n tends to infinity. The inequality is true though and I'm pretty sure it can be proved fairly easily using calculus methods (show it has no stationary point in the domain (0,infinity)).

 

Well, didn't want to prove this inequity because i though its obvious that . I will try to see if i can approach it in a different way. 

 

 

OH man, what a terrible mistake!!!

however, have a look at this..

You're close, I think it is possible to prove it the way you have. You've missed something though, you haven't proved that the inequality holds for all n, rather you proved that it does when n tends to infinity. The inequality is true though and I'm pretty sure it can be proved fairly easily using calculus methods (show it has no stationary point in the domain (0,infinity)).

 

Well, didn't want to prove this inequality because i though its obvious that . I will try to see if i can approach it in a different way.