Putnam 2008, Problem A-4

Define $f: \mathbb{R} \to \mathbb{R}$ by
\[
f(x) = \begin{cases} 
x & \text{if } x \leq e \\
x f(\ln x) & \text{if } x > e 
\end{cases}
\]
Does $\sum_{n=1}^\infty \frac{1}{f(n)}$ converge?

Solution:
The sum diverges. From the definition, $f(x) = x$ on $[1,e]$, $x \ln x$ on $(e,e^e]$, $x \ln x \ln \ln x$ on $(e^e, e^{e^e}]$, and so forth. It follows that on $[1,\infty)$, $f$ is positive, continuous, and increasing. Thus $\sum_{n=1}^{\infty} \frac{1}{f(n)}$, if it converges, is bounded below by $\int_1^{\infty} \frac{dx}{f(x)}$; it suffices to prove that the integral diverges.

Write $\ln^1 x = \ln x$ and $\ln^k x = \ln(\ln^{k-1} x)$ for $k \geq 2$; similarly write $\exp^1 x = e^x$ and $\exp^k x = e^{\exp^{k-1} x}$. If we write $y = \ln^k x$, then $x = \exp^k y$ and $dx = (\exp^k y)(\exp^{k-1} y) \cdots (\exp^1 y) dy = x(\ln^1 x) \cdots (\ln^{k-1} x) dy$. Now on $[\exp^{k-1} 1, \exp^k 1]$, we have $f(x) = x(\ln^1 x) \cdots (\ln^{k-1} x)$, and thus substituting $y = \ln^k x$ yields
$$\int_{\exp^{k-1} 1}^{\exp^k 1} \frac{dx}{f(x)} = \int_0^1 dy = 1.$$

It follows that $\int_1^{\infty} \frac{dx}{f(x)} = \sum_{k=1}^{\infty} \int_{\exp^{k-1} 1}^{\exp^k 1} \frac{dx}{f(x)}$ diverges, as desired.