## Sunday, December 10, 2006

### 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]