MemberMarch 8, 2021 at 5:44 pm
Suppose f(x) is the non decreasing function such that f(x)>0 , for all x.
Prove that there exists x, such that f(x+1/f(x))<2f(x).
This is interesting and challenging…
MemberMarch 9, 2021 at 1:19 am
Interesting. I’ll have to go away and ponder that by visualising some examples first.
MemberMarch 9, 2021 at 5:59 pm
James, There is a solution below. Yet Let us know if you find some other way to solve it.
AdministratorMarch 9, 2021 at 6:46 am
That’s interesting question… Here is the easiest solution I could find:
- f(x) ⇾ C > 0 as x ⇾ ∞
Then, for large x, the left handside will approach C and the right handside will approach 2C > C. Easy.
- f(x) ⇾ ∞ as x ⇾ ∞
Take a sequence (x₀, x₁, x₂, …), such that f(xₙ) = 2ⁿT. Then, if the claim is not true, we must have xₙ + 1/2ⁿT > xₙ₊₁ for every n. We sum over n and get x₀ + 2/T > xₙ. Therefore, xₙ is bounded which is impossible.
The solution assumed that f(x) is continuous but it is not hard to modify it and drop the assumption:)
MemberMarch 9, 2021 at 6:00 pm
Fantastic , Artur!! Good Job…Love it 🙂
MemberMarch 9, 2021 at 7:50 pm
I really admire the ability to think up these proofs. I can follow through the final proof and understand it, but I’d have very little chance of coming up with it myself. Nice work.
AdministratorMarch 9, 2021 at 9:21 pm
For this puzzle it is actually quite handy to make a drawing… The idea is to start with an arbitrary number x0 and if it doesn’t work, then you can see that the number x1, such that f(x1)=2f(x0), must be very close. Then, you try x1 and if it also doesn’t work, then x2 must be even closer. You continue trying numbers x3, x4, etc. and either one of them eventually works out, or it turns out that the function f(x) has a vertical asymptote, which is impossible.
I hope this gives a bit more insight:)
MemberMarch 9, 2021 at 10:29 pm
Thanks, that’s a really useful way of expressing it. I wish I’d learnt more about pure maths and proof when I was younger. I find it gets harder to learn this stuff the older one gets. I’m lucky that I still get to do a lot of interesting maths as part of my day job, but it’s mostly physics and geometry type stuff, with the occasional foray into the edges of topology or group theory if I’m lucky.
AdministratorMarch 9, 2021 at 10:40 pm
The way you describe your job, I quite envy you to be honest! I recently left the academy, so no hopes to do/study physics, geometry, topology, or group theory…
About getting older… unless you are 60, I wouldn’t worry much:) These math puzzles rely a lot on practice, so if you haven’t participated in competitions in school/college, it is normal to find some of them tricky.
MemberMarch 9, 2021 at 11:37 pm
Artur, Based on the clue from your solution, to observe the tail end behaviour, I tried something. But not sure of its completeness. I might have missed something.
lim G(x) as x->infinity is
lim f(x+1/f(x)) – 2 * lim f(x)
Suppose f(x)->infinity, lim f(x+1/f(x))=lim f(x) as x->infinity
So, lim G(x) = -lim f(x) <0 , as f(x)>0
So, There must exist G(x)<0, that is f(x+1/f(x))<2f(x)
Something incomplete here….??
*This is exactly your solution as in part 1, but trying to extend that to part 2 as well…
AdministratorMarch 10, 2021 at 8:03 am
Hey Vivek, I think the issue is that when f(x) is unbounded, then you can’t say that lim G(x) = – lim f(x), since you can’t subtract infinities:)
MemberMarch 10, 2021 at 8:46 am
You are right, Artur. We should be careful while dealing with infinities. It is certainly the case like when we have something like f(x+x^2)-2f(x). I thought we can approach in that way , if we have f(x+g(x))-2f(x) as g(x) goes to 0 as x->infinity. I tried to prove it from the scratch from the limit definition. But Not sure of it. I might be wrong. Anyway I tried the same in slightly different way. Let me know your opinion on this…
MemberMarch 10, 2021 at 8:48 am
**in the first image, That is for all x>M.
AdministratorMarch 10, 2021 at 10:34 am
This approach uses multiple beautiful ideas, but tbh I am not sure it actually works:(
For one, we assume that f(x) is differentiable which is quite strong. Then, I don’t think we can take the limit and get f'(x)/f(x) in the expression. The derivative is evaluated at every point separately, so the best we can do is write something like f'(x+g(x))/f(x), where g(x) converges to 0. Maybe one can continue from there though and modify the second part of the proof (which I enjoyed a lot!).
- f(x) ⇾ C > 0 as x ⇾ ∞
MemberMarch 10, 2021 at 10:53 am
Artur, For the assumption f(x) is differentiable, We only need that it is differentiable at right hand side and that I think is possible because of the way the function is defined. Like both f(x+h) and f(x) are going to exist.
And for the second , I used the limit definition of right hand derivative. f'(x) is lim (f(x+h)-f(x))/h as h->0+ (right hand limit). Instead of h, We have 1/f(x) which also approaches 0 as f(x) goes to infinity.. wondering why we can’t use that?? Little bit confused here…
Also we can prove that this limit indeed goes to -infinity by letting L>-a and getting contradiction.
Anyway If this does not go to -infinity for any non decreasing f(x), Can we find f(x), such that L is not -infinity?
AdministratorMarch 10, 2021 at 12:58 pm
I believe the function even doesn’t need to be continuous; only non-decreasing and positive is enough.
Regarding the second point, I agree that 1/f(x) approaches 0 as x grows, but the issue is that f'(x) = lim (f(x+h)-f(x))/h with limit over h for fixed x. In our case we are taking the limit over x as it grows to inifinity, so we can’t quite say that the expression approaches f'(x). In order to see exactly what is happening, we can use the Mean Value Theorem and for every x replace (f(x+1/f(x))-f(x))/(1/f(x)) with f'(x+g(x)), where g(x) < 1/f(x). Then, we will get f'(x+g(x))/f(x)-f(x), but we can’t dismiss g(x), even though it goes to 0.
I can elaborate more on this and probably come up with a counter-example, as it is quite a tricky point. Let me know and I will be happy to do it:)
MemberMarch 10, 2021 at 3:10 pm
Confusing , Artur 🙁 I think I have to give some time gap to this problem. Can come to this freshly again later. I try to think about it. I too tried to get some counter example to better understand. Could not though. If you come across one, Please share it , Artur. Anyway the problem is already closed as you provided the solution. This is for the understanding of some concepts.
MemberMarch 10, 2021 at 6:32 pm
In the second part, I argued L>=0 is not possible. So, L<0. I think that is not completely true. L may not exist at all, oscillating between positive and negative values forever. Even in this case, The existence of negative value, proves our point.
The problem is this contradicts with the earlier attempt in which I said L goes to -infinity for sure. So, Either that or this must be wrong. Now I understand there is some problem…
AdministratorMarch 13, 2021 at 9:22 am
You already told me over PM that you have figured things out, but I will leave this here in case someone ever reads it:)
If you pick f(x) = x³ and g(x) = 1/x, then we have:
lim (f(x+g(x)) – f(x))/g(x) – f'(x) = lim x(x³+3x+3/x+1/x³-x³) – 3x² = 3
The example is not perfect, but it illustrates why you can’t replace (f(x+g(x)) – f(x))/g(x) with f'(x) even when g(x) ⇾ 0.
MemberMarch 13, 2021 at 2:52 pm
Thank you for the nice illustration, Artur 🙂
MemberMarch 10, 2021 at 11:01 am
You are right about the existence of derivative. Even though the function is continuous, it may not be differentiable at corner/junction points. I think it can be avoided by taking one sided derivative, for the sake of this problem.
AdministratorMarch 10, 2021 at 1:01 pm
The issue is that the function even doesn’t need to be continuous, which is weaker than differentiability…
MemberMarch 12, 2021 at 10:33 pm
AdministratorMarch 13, 2021 at 9:11 am
That’s right, great solution! A bit of analysis… The key difference between the two solutions is that for my sequence I pick the x‘s for which the value f(x) gets doubled every time. These x‘s are smaller than yours; you have chosen them such that x(i+1) = x(i) + 1/f(x(i)) (which seems a bit more natural). However, in both cases the sequences x(i) converge, which brings a contradiction since f(x) can’t have a vertical asymptote.
It is nice to have both approaches here, thank you for sharing! 🙂
MemberMarch 13, 2021 at 2:55 pm
🙂 I have some minor confusions, Artur. Can we always find xn such that f(xn)= 2^n*T ? This may not be possible if f has jump discontinuities , right?
AdministratorMarch 13, 2021 at 3:37 pm
You are right… My idea for the modification was to pick the sequence x(i), such that x(i+1) ≤ x(i)+1/f(x(i)) and f(x(i+1)) ≥ 2f(x(i)), since that’s all we need for the computation. I see now that:
- The sequence x(i+1)=x(i)+1/f(x(i)) satisfies this condition.
- We are actually FORCED to pick x(i+1)=x(i)+1/f(x(i)), since in the worst case we can get f(x(i)+1/f(x(i)) ≥ 2f(x(i)) and f(y) < 2f(x(i)) for y < x(i)+1/f(x(i).
So, your solution is actually the only possible modification of my solution that works for discontinuous functions 😀