Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Nov 8, 2013

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.

8 comments:

  1. Rename the variables in the first limit (x->c, n->x):

    forall 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

    ReplyDelete
  2. 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

    ReplyDelete
  3. if 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.

    ReplyDelete
  4. In 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.

    ReplyDelete
  5. I 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:
    f(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.

    ReplyDelete
    Replies
    1. 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.

      Delete
  6. 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.

    ReplyDelete
  7. The 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.

    ReplyDelete