Just... Right. Topic: Calculus/Inequalities. Level: AIME/Olympiad.

Problem: (Stanford Putnam Practice) Let $ f $ be continuous and monotonically increasing, with $ f(0) = 0 $ and $ f(1) = 1 $. Prove that

$ \displaystyle f(1/10)+f(2/10)+\cdots+f(9/10)+f^{-1}(1/10)+f^{-1}(2/10)+\cdots+f^{-1}(9/10) \le \frac{99}{10} $.

Solution: We can easily generalize this to

$ \displaystyle \sum_{k=1}^{n-1} [f(k/n)+f^{-1}(k/n)] \le \frac{n^2-1}{n} $,
so we will prove this instead. Consider the value of $ \displaystyle \int_0^1 [f(x)+f^{-1}(x)]dx $. This integrates across the area of the unit square with opposite vertices $ (0,0) $ and $ (1,1) $ so the integral is $ 1 $. Visualize this with a picture. Now we use a left-hand Riemann sum approximation on both $ f(x) $ and $ f^{-1}(x) $ with $ n-1 $ subdivisions from $ \frac{1}{n} $ to $ 1 $ to get

$ \displaystyle \int_0^{\frac{1}{n}} [f(x)+f^{-1}(x)]dx+\frac{1}{n}\sum_{k=1}^{n-1} [f(k/n)+f^{-1}(k/n)] \le \int_0^1 [f(x)+f^{-1}(x)]dx = 1 $.

Then it remains to show that

$ \displaystyle \int_0^{\frac{1}{n}} [f(x)+f^{-1}(x)]dx \ge \frac{1}{n^2} $.

But from the argument above we know covers at least the square with opposite vertices $ (0,0) $ and $ \left(\frac{1}{n},\frac{1}{n}\right) $, which has area $ \frac{1}{n^2} $. Again, draw a picture (it's the same as before except without the endpoint restriction). Hence we have shown that

$ \displaystyle \sum_{k=1}^{n-1} [f(k/n)+f^{-1}(k/n)] \le \frac{n^2-1}{n} $,

as desired. QED.

--------------------

Comment: This was a pretty interesting problem; it was pretty clear from the beginning that you were approximating some kind of interval and it looked a lot like Riemann sums so that seemed to be the method of choice. After that, a little knowledge about function inverses and a couple of nice pictures gave the rest of the solution.

--------------------

Practice Problem: (Stanford Putnam Practice) Let $ a_0 $ be an arbitrary positive integer and let

$ a_{n+1} = \frac{1}{a_n}+1 $ for $ n \ge 0 $.

Determine if $ \lim_{n \rightarrow \infty} a_n $ exists and if so, evaluate it. [Reworded]