Putnam 2025, Problem B-6

Let \( \mathbb{N} = \{1, 2, 3, \ldots\} \). Find the largest real constant \( r \) such that there exists a function \( g: \mathbb{N} \to \mathbb{N} \) such that
\[
g(n + 1) - g(n) \geq (g(g(n)))^r
\]
for all \( n \in \mathbb{N} \).


Solution:
The largest such constant is \( r = \frac{1}{4} \). This value works because we may take \( g(n) = n^2 \).

By way of contradiction, suppose such a function \( g \) exists for some \( r > \frac{1}{4} \). Since \( g \) takes positive integer values, \( g(n + 1) - g(n) > g(g(n))^r > 0 \) for all \( n \).

We next note that for \( s \in [0, \infty) \) the minimum of \( rs^2 + 1 - s \) is \( 1 - \frac{1}{4r} > 0 \) (achieved at \( s = \frac{1}{2r} \)), so the sequence
\[
s_0 = 0, \quad s_{n+1} = r s_n^2 + 1
\]
is strictly increasing and unbounded.

In the following arguments, we make a number of statements over positive integers \( n \) and an auxiliary real parameter \( s \geq 0 \). For notational convenience, we adopt the convention that \( * \) always represents a positive constant dependent on \( s \) but not \( n \), but no two appearances of \( * \) necessarily represent the same positive constant.

We next prove that for any \( s \geq 0 \), we have \( g(n) \geq n^s \) for \( n \geq * \). This is evident for \( s = 0 \); since the sequence \( \{s_n\} \) is unbounded, it is sufficient to “induct” by deducing that the claim for some \( s \) implies the same for \( rs^2 + 1 - \varepsilon \) for any \( \varepsilon > 0 \). To wit, if \( g(n) \geq * n^s \) for \( n \geq * \), then by telescoping and monotonicity, for \( n \geq * \) we have
\[
g(n) \geq \sum_{m=*}^{n-1} g(g(m))^r \geq \sum_{m=*}^{n-1} g(\lfloor * m^s \rfloor)^r \geq \sum_{m=*}^{n-1} (* m^{rs^2})^r \geq * n^{rs^2 + 1 - \varepsilon}.
\]
Applying the previous paragraph for some \( s > 4 \), for \( n \geq * \) we obtain
\[
g(n) > g(n) - g(n - 1) \geq g(g(n - 1))^r > g((n - 1)^s)^r > g(n^4)^{1/4}
\]
and thus \( g(n^4) < g(n)^4 \). Fix some \( n \geq * \) and choose \( M \) for which \( g(n) < n^M \); we can then induct on \( k \) to obtain \( g(n^{4^k}) < (n^M)^{4^k} \), contradicting the previous paragraph.

**Remark.** There are numerous paths from the bound \( g(n) \geq n^s \) to the final contradiction. We give one alternative here: for some \( s > 16 \), for \( n \geq * \) we have
\[
g(n) > g(n) - g(n - 1) \geq g(g(n - 1))^r \geq g(n - 1)^{rs} \geq g(n - 1)^{4s - 1} g(n - 1) \geq 3g(n - 1),
\]
yielding \( g(n) > 2^n \) and hence (still for \( n \geq * \))
\[
g(n) > g(n) - g(n - 1) \geq g(g(n - 1))^r \geq g(2^n)^r \geq g(2^{n - 1})^{16s - 1} g(2^{n - 1}) > 2g(2^{n - 1} - 1) \geq 2g(n),
\]
a contradiction.