Putnam 2018, Problem A-5

Let $f : \mathbb{R} \to \mathbb{R}$ be an infinitely differentiable function satisfying $f(0) = 0$, $f(1) = 1$, and $f(x) \geq 0$ for all $x \in \mathbb{R}$. Show that there exist a positive integer $n$ and a real number $x$ such that $f^{(n)}(x) < 0$.

Solution:
**First solution.** Call a function $f: \mathbb{R} \to \mathbb{R}$ *ultraconvex* if $f$ is infinitely differentiable and $f^{(n)}(x) \geq 0$ for all $n \geq 0$ and all $x \in \mathbb{R}$, where $f^{(0)}(x) = f(x)$; note that if $f$ is ultraconvex, then so is $f'$. Define the set
$$
S = \{ f: \mathbb{R} \to \mathbb{R} \,|\, f \text{ ultraconvex and } f(0) = 0 \}.
$$
For $f \in S$, we must have $f(x) = 0$ for all $x < 0$: if $f(x_0) > 0$ for some $x_0 < 0$, then by the mean value theorem there exists $x \in (0,x_0)$ for which $f'(x) = \frac{f(x_0)}{x_0} < 0$. In particular, $f'(0) = 0$, so $f' \in S$ also.

We show by induction that for all $n \geq 0$,
$$
f(x) \leq \frac{f^{(n)}(1)}{n!} x^n \quad (f \in S, x \in [0,1]).
$$
We induct with base case $n=0$, which holds because any $f \in S$ is nondecreasing. Given the claim for $n=m$, we apply the induction hypothesis to $f' \in S$ to see that
$$
f'(t) \leq \frac{f^{(n+1)}(1)}{n!} t^n \quad (t \in [0,1]),
$$
then integrate both sides from 0 to $x$ to conclude.

Now for $f \in S$, we have $0 \leq f(1) \leq \frac{f^{(n)}(1)}{n!}$ for all $n \geq 0$. On the other hand, by Taylor's theorem with remainder,
$$
f(x) \geq \sum_{k=0}^{n} \frac{f^{(k)}(1)}{k!} (x-1)^k \quad (x \geq 1).
$$
Applying this with $x=2$, we obtain $f(2) \geq \sum_{k=0}^{n} \frac{f^{(k)}(1)}{k!}$ for all $n$; this implies that $\lim_{n \to \infty} \frac{f^{(n)}(1)}{n!} = 0$. Since $f(1) \leq \frac{f^{(n)}(1)}{n!}$, we must have $f(1) = 0$.

For $f \in S$, we proved earlier that $f(x) = 0$ for all $x \leq 0$, as well as for $x = 1$. Since the function $g(x) = f(cx)$ is also ultraconvex for $c > 0$, we also have $f(x) = 0$ for all $x > 0$; hence $f$ is identically zero.

To sum up, if $f: \mathbb{R} \to \mathbb{R}$ is infinitely differentiable, $f(0) = 0$, and $f(1) = 1$, then $f$ cannot be ultraconvex. This implies the desired result.

**Variant.** (by Yakov Berchenko-Kogan) Another way to show that any $f \in S$ is identically zero is to show that for $f \in S$ and $k$ a positive integer,
$$
f(x) \leq \frac{x}{k} f'(x) \quad (x \geq 0).
$$
We prove this by induction on $k$. For the base case $k=1$, note that $f''(x) \geq 0$ implies that $f'$ is nondecreasing. For $x \geq 0$, we thus have
$$
f(x) = \int_0^x f'(t) \, dt \leq \int_0^x f'(x) \, dt = x f'(x).
$$
To pass from $k$ to $k+1$, apply the induction hypothesis to $f'$ and integrate by parts to obtain
$$
\begin{aligned}
k f(x) &= \int_0^x k f'(t) \, dt \\
&\leq \int_0^x t f''(t) \, dt \\
&= x f'(x) - \int_0^x f'(t) \, dt = x f'(x) - f(x).
\end{aligned}
$$
This yields $f(x) \leq \frac{x}{k+1} f'(x)$, completing the induction.

**Remark.** Noam Elkies points out that one can refine the argument to show that if $f$ is ultraconvex, then it is analytic (i.e., it is represented by an entire Taylor series about any point, as opposed to a function like $f(x) = e^{-1/x^2}$ whose Taylor series at 0 is identically zero); he attributes the following argument to Peter Shalen. Let $g_n(x) = \sum_{k=0}^{n} \frac{1}{k!} f^{(k)}(0) x^k$ be the $n$-th order Taylor polynomial of $f$. By Taylor's theorem with remainder (a/k/a Lagrange's theorem), $f(x) - g_n(x)$ is everywhere nonnegative; consequently, for all $x \geq 0$, the Taylor series $\sum_{n=0}^{\infty} \frac{1}{n!} f^{(n)}(0) x^n$ converges and is bounded above by $f$. But since $f^{(n+1)}(x)$ is nondecreasing, Lagrange's theorem also implies that $f(x) - g_n(x) \leq \frac{1}{(n+1)!} f^{(n+1)}(x)$; for fixed $x \geq 0$, the right side tends to 0 as $n \to \infty$. Hence $f$ is represented by its Taylor series for $x \geq 0$, and so is analytic for $x > 0$; by replacing $f(x)$ with $f(x-c)$, we may conclude that $f$ is everywhere analytic.

**Remark.** We record some properties of the class of ultraconvex functions.
- Any nonnegative constant function is ultraconvex. The exponential function is ultraconvex.
- If $f$ is ultraconvex, then $f'$ is ultraconvex. Conversely, if $f'$ is ultraconvex and $\liminf_{x \to -\infty} f(x) \geq 0$, then $f$ is ultraconvex.
- The class of ultraconvex functions is closed under addition, multiplication, and composition.

**Second solution.** (by Zachary Chase) In this solution, we use *Bernstein's theorem on monotone functions*. To state this result, we say that a function $f: [0,\infty) \to \mathbb{R}$ is *totally monotone* if $f$ is continuous, $f$ is infinitely differentiable on $(0,\infty)$, and $(-1)^n f^{(n)}(x)$ is nonnegative for all positive integers $n$ and all $x > 0$. For such a function, Bernstein's theorem asserts that there is a nonnegative finite Borel measure $\mu$ on $[0,\infty)$ such that
$$
f(x) = \int_0^\infty e^{-tx} d\mu(t) \quad (x \geq 0).
$$
For $f$ as in the problem statement, for any $M > 0$, the restriction of $f(M-x)$ to $[0,\infty)$ is totally monotone, so Bernstein's theorem provides a Borel measure $\mu$ for which $f(M-x) = \int_0^\infty e^{-tx} d\mu(t)$ for all $x \geq 0$. Taking $x=M$, we see that $\int_0^\infty e^{-Mt} d\mu(t) = f(0) = 0$; since $\mu$ is a nonnegative measure, it must be identically zero. Hence $f(x)$ is identically zero for $x \leq M$; varying over all $M$, we deduce the desired result.

**Third solution.** (from Art of Problem Solving user chronondecay) In this solution, we only consider the behavior of $f$ on $[0,1]$. We first establish the following result. Let $f: (0,1) \to \mathbb{R}$ be a function such that for each positive integer $n$, $f^{(n)}(x)$ is nonnegative on $(0,1)$, tends to 0 as $x \to 0^+$, and tends to some limit as $x \to 1^-$. Then for each nonnegative integer $n$, $f(x)x^{-n}$ is nondecreasing on $(0,1)$.

To prove the claimed result, we proceed by induction on $n$, the case $n=0$ being a consequence of the assumption that $f'(x)$ is nonnegative on $(0,1)$. Given the claim for some $n \geq 0$, note that since $f'$ also satisfies the hypotheses of the problem, $f'(x)x^{-n}$ is also nondecreasing on $(0,1)$. Choose $c \in (0,1)$ and consider the function
$$
g(x) = \frac{f'(c)}{c^n} x^n \quad (x \in [0,1)).
$$
For $x \in (0,c)$, $f'(x)x^{-n} \leq f'(c)c^{-n}$, so $f'(x) \leq g(x)$; similarly, for $x \in (c,1)$, $f'(x) \geq g(x)$. It follows that if $f'(c) > 0$, then
$$
\frac{\int_c^1 f'(x) \, dx}{\int_0^c f'(x) \, dx} \geq \frac{\int_c^1 g(x) \, dx}{\int_0^c g(x) \, dx} \Rightarrow \frac{\int_0^c f'(x) \, dx}{\int_0^1 f'(x) \, dx} \leq \frac{\int_0^c g(x) \, dx}{\int_0^1 g(x) \, dx}
$$
and so $f(c)/f(1) \leq c^{n+1}$. (Here for convenience, we extend $f$ continuously to $[0,1]$.) That is, $f(c)/c^{n+1} \leq f(1)$ for all $c \in (0,1)$. For any $b \in (0,1)$, we may apply the same logic to the function $f(bx)$ to deduce that if $f'(c) > 0$, then $f(bc)/c^{n+1} \leq f(b)$, or equivalently
$$
\frac{f(bc)}{(bc)^{n+1}} \leq \frac{f(b)}{b^{n+1}}.
$$
This yields the claim unless $f'$ is identically 0 on $(0,1)$, but in that case the claim is obvious anyway.

We now apply the claim to show that for $f$ as in the problem statement, it cannot be the case that $f^{(n)}(x)$ is nonnegative on $(0,1)$ for all $n$. Suppose the contrary; then for any fixed $x \in (0,1)$, we may apply the previous claim with arbitrarily large $n$ to deduce that $f(x) = 0$. By continuity, we also then have $f(1) = 0$, a contradiction.

**Fourth solution.** (by Alexander Karabegov) As in the first solution, we may see that $f^{(n)}(0) = 0$ for all $n$. Consequently, for all $n$ we have
$$
f(x) = \frac{1}{(n-1)!} \int_0^x (x-t)^{n-1} f^{(n)}(t) \, dt \quad (x \in \mathbb{R})
$$
and hence
$$
\int_0^1 f(x) \, dx = \frac{1}{n!} \int_0^1 (1-t)^n f^{(n)}(t) \, dt.
$$
Suppose now that $f$ is infinitely differentiable, $f(1) = 1$, and $f^{(n)}(x) \geq 0$ for all $n$ and all $x \in [0,1]$. Then
$$
\begin{aligned}
\int_0^1 f(x) \, dx &= \frac{1}{n} \cdot \frac{1}{(n-1)!} \int_0^1 (1-t)^n f^{(n)}(t) \, dt \\
&\leq \frac{1}{n} \cdot \frac{1}{(n-1)!} \int_0^1 (1-t)^{n-1} f^{(n)}(t) \, dt \\
&= \frac{1}{n} f(1) = \frac{1}{n}.
\end{aligned}
$$
Since this holds for all $n$, we have $\int_0^1 f(x) \, dx = 0$, and so $f(x) = 0$ for $x \in [0,1]$; this yields the desired contradiction.

---