Calculus Limit Puzzle
Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008)
Problem:
Tricky Question.
Let f be a continuous, real-valued function on reals such that
limit_{n \rightarrow \infty} f(nx) = 0 for all real x.
Show limit_{x\rightarrow \infty} f(x) = 0.
Problem:
Tricky Question.
Let f be a continuous, real-valued function on reals such that
limit_{n \rightarrow \infty} f(nx) = 0 for all real x.
Show limit_{x\rightarrow \infty} f(x) = 0.
Rename the variables in the first limit (x->c, n->x):
ReplyDeleteforall c in reals, lim[x->inf] f(x*c) = 0
Then do forall elimination, with c=1:
lim[x->inf] f(x*1) = 0
lim[x->inf] f(x) = 0
can it be as simple as put x = 1 in the first case, so we are left with f(n), where n->infinity is same as f(x) where x->infinity
ReplyDeleteif limit_{n \rightarrow \infty} f(nx) = 0 for all real x, if i put x=1, i will be left with limit_{n \rightarrow \infty} f(n) = 0 which is same as limit_{x\rightarrow \infty} f(x) = 0.
ReplyDeleteIn reference to Strilanc and nishu, I think what the problem meant to say is that, for all x, limit_{n->infinity} f(nx) = 0, where n is a natural number. In other words, for all x, the sequence f(x), f(2x), f(3x), . . . , f(nx), . . . converges to zero. This means that we can't simply solve this by plugging in x=1, since the sequence f(1), f(2), . . . approaching zero is not the same as the function f(x) approaching zero.
ReplyDeleteI agree with Mike Earnest. n should be a natural number(positive integer), otherwise this problem is trivial. However this seems to be a counterexample to the statement:
ReplyDeletef(x)=1 if x=sqrt(p) for some prime number p, and f(x)=0 otherwise. We can see that lim_{x \rightarrow \infty} is not zero, because there exists a sequence {\sqrt{p_i}} such that f(sqrt{p_i})=1 all the time. However, lim_{n \rightarrow \infty}f(nx)=0 for real number x, because if nx=sqrt{p} for some n and p, then when m>n, mx will never be the square root of another prime number q. Actually, if nx=sqrt{p} and mx=sqrt{q}, then n/m=sqrt{p/q}, where the LHS is a rational number but the RHS is an irrational number.
Therefore, if f(nx)=1, then f(mx)=0 for all m>n. That means lim_{n \rightarrow \infty}f(nx)=0. But lim_{x \rightarrow \infty} is not zero.
But the problem assumes the function f is continuous, and your function is not! That's why this problem is so hard, since you can imagine many continuous functions that are very "close" to the function you just described (like a sequence of triangular spikes of height 1 at sqrt(p), with widths that approach zero), but it's hard to tell if these satisfy f(nx) -> 0 for all x.
DeleteBut the problem assumes the function f is continuous, and your function is not! That's why this problem is so hard, since you can imagine many continuous functions that are very "close" to the function you just described (like a sequence of triangular spikes of height 1 at sqrt(p), with widths that approach zero), but it's hard to tell if these satisfy f(nx) -> 0 for all x.
ReplyDeleteThe basic idea for this problem is to create a family of functions f_n(x) = nx for a fixed x, and have an infinite family of such functions. Then notice that the image of any closed interval [a,b] will be [na,nb] under the the function f_n. Then notice that any tiny interval, no matter how small, will cover the real number line starting at some point c, under the union of the images of all the f_n's with n>N for some n. The details don't really matter, the point is that if you assume that f(x) is not converging to 0, then for some epsilon, there will always be somewhere where f(x) > epsilon, which means it is greater than epsilon for a small neighborhood since it is continuous. Then that neighborhood of x lies in the image of some f_n(x) and you can "pull it back" that is, take the preimage of that little interval. It will lie in whatever interval you started with. I started with [0,1] for my proof. Then take your new, subinterval, and for some set of f_n's, the image of this subinterval will cover all of R. Find another point on f(x) where f(x) > epsilon, this time farther out by at least one from the previous one. It must exist because of our assumption, so then again, we can find a small neighborhood inside the image of one of the f_n's and then pull that back, to get another nested interval. This can be repeated infinitely many times and we get both a sequence of points, x_0, x_1, ... where f(x_i) > epsilon, and a sequence of n's, n_0, n_1... and a sequence of intervals where if x in Interval_i, then f(x) > epsilon "near" the point x_i. Take the intersection of all those nested intervals. It is a countably infinite intersection of closed nested sets so it is non-empty. take any x in the intersection, and it will have the property that f(n_i x)>epsilon for all n_i (there are infinitely many!) that is the contradiction... it now implies that the sequence f(nx) does NOT go to zero, which was a given for the problem. Therefore, our assumption that f(x) -\-> 0 is false, and so f(x) -> 0 as x->infinity.
ReplyDeletein other words , required to prove that if f is continous function and f(x)->0 is false, then there exists a real number x such that f(n*x)->0 is false. Interestingly, the above proof by jinbal shows that not only such x will exist but it will exist almost everywhere i.e. if f is continouus function and f(x)->0 is false, then given any interval (a,b), there will be a real number x in this interval such that f(n*x)->0 is false.
ReplyDeletehowever some details tin he above proof of jinbal is explained below:-
given any interval [a,b], there exists a number R, such that every number greater than R is an integral multiple of some number in interval [a,b]. this is true because if we consider sequence of intervals I_n= [n*a,n*b], then if n>= a/(b-a), then, (n+1)*a<= n*b, so from the nth interval onwards, the intervals start overlapping and hence will cover the real line to the right of a*a/(b-a).
because f->0 is false, there exists epsilon such that given any real R, there will exist x > R such that f(x) > epsilon.
therefore select a number x > a*a/(b-a) such that f(x) > epsilon,
since x>a*a/(b-a), x/n_1 lies in interval [a,b] for some integer n_1.
since f is continuous, there is an sub-interval [a_1,b_1] of [a,b] such that f > epsilon in the interval [n_1*a_1,n_1*b_1].
apply the above procedure recursively to get a nested sequence [a_i,b_i] and a strictly monotonic sequence n_i such that if x is in [a_i,b_i], then f(n_i * x) > epsilon.
if a number x belongs to the inersection of the above nested intervals, then f(n_i*x)>epsilon and hence f(n*x)->0 is false.
therefore it only remains to be shown that the sequence of nested intervals [a_n,b_n] has a non- empty intersection. it is a standard result in real analysis however proof is simple as folllows:
so, let a= supremum {a_1,a_2,a_3,....}, b= infimum{b_1,b_2,b_3,......}. then any element in first set <= any element in latter set. So a<=b. and take any x in [a,b], then x >=a, and a >= a_i , so x>=a_i. similarly x<=b_i. so x is in [a_i,b_i] for all i.