IMO 1993 Problem 5

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m02s

Problem

Does there exist a function $f:\textbf{N}\rightarrow\textbf{N}$ such that $f(1)=2,f(f(n))=f(n)+n$ for all $n\in\textbf{N}$ and $f(n)<f(n+1)$ for all $n\in\textbf{N}$?

Exploration

The functional equation $f(f(n)) = f(n) + n$ forces a strong coupling between values at $n$ and at $f(n)$. Because $f$ is strictly increasing on $\mathbb{N}$, iterates of $f$ must grow without repetition, and the equation suggests that the sequence $(f(n))$ encodes additive information about indices.

Substituting small values reveals constraints. From $f(1) = 2$, applying the functional equation at $n=1$ gives $f(f(1)) = f(2) = f(1) + 1 = 3$, hence $f(2) = 3$. Continuing, $f(f(2)) = f(3) = f(2) + 2 = 5$, so $f(3) = 5$. Then $f(f(3)) = f(5) = f(3) + 3 = 8$. This already suggests a pattern reminiscent of a permutation with controlled gaps.

However, the growth is not linear, and values such as $4,6,7$ are not yet determined but must be placed consistently while preserving strict monotonicity and the functional identity. The equation implies that every value $f(n)$ participates as an input producing a shifted output, so missing values must be accounted for by indirect constraints.

A central difficulty is that $f$ must be injective due to strict monotonicity, but also its image must be closed under a shifted inverse operation induced by the functional equation. The most promising approach is to show that iterating the relation forces a contradiction in growth or parity distribution.

A key observation is to consider the sequence $a_n = f(n) - n$, which may transform the equation into a recursive relation. However, substitution shows coupling remains nonlinear.

The likely strategy is to propagate the functional equation along chains $n \to f(n) \to f(f(n))$ and analyze additive accumulation, aiming to derive an impossible inequality.

Problem Understanding

This is a Type B problem: it asks whether a function satisfying given constraints exists.

We are given a function $f:\mathbb{N}\to\mathbb{N}$ such that $f(1)=2$, the function is strictly increasing, and it satisfies $f(f(n)) = f(n) + n$ for all natural numbers $n$. The task is to determine whether such a function can exist.

The difficulty comes from the interaction between monotonicity and the self-referential functional equation. The condition ties the value at $f(n)$ directly to both $f(n)$ and $n$, forcing a rigid structure that must be globally consistent across all natural numbers. While small values can be computed recursively, extending this consistently without violating strict increase becomes highly constrained.

The intuition suggests that repeated application of the functional equation forces incompatible growth rates: the function must simultaneously behave like a permutation with controlled additive shifts and like a strictly increasing sequence filling all natural numbers.

The expected conclusion is that no such function exists.

Proof Architecture

Lemma 1 states that $f$ is injective. This follows immediately from strict monotonicity.

Lemma 2 states that the iterates $n, f(n), f(f(n))$ are strictly increasing in a controlled way, and in particular $f(n) > n$ for all $n \ge 1$. This is derived from the functional equation and monotonicity.

Lemma 3 states that for any $n$, repeated application of the functional equation produces a growth relation $f^{k+1}(n) = f^k(n) + f^{k-1}(n)$ for appropriate indices along the orbit, yielding rapidly increasing sequences.

Lemma 4 states that the sequence of values eventually forces a contradiction with strict monotonicity by producing two distinct inputs whose images must overlap or violate order.

The hardest step is Lemma 4, since it requires global control over all iterates and interaction between functional recursion and ordering.

Solution

Lemma 1: The function $f$ is injective.

If $f(a) = f(b)$ with $a < b$, then strict monotonicity gives $f(a) < f(b)$, a contradiction. Therefore $a=b$, and $f$ is injective. ∎

This establishes that no two distinct inputs share the same image, and any hidden shortcut assuming possible collisions fails because order forces strict separation.

Lemma 2: For all $n \in \mathbb{N}$, one has $f(n) > n$.

From $f(f(n)) = f(n) + n$, the right-hand side is strictly greater than $f(n)$, so $f(f(n)) > f(n)$. Since $f$ is strictly increasing and injective, applying inverse-order reasoning on indices forces $f(n) > n$, otherwise if $f(n) \le n$, then iterating would contradict strict growth of images. More concretely, if $f(n) \le n$, then applying monotonicity gives $f(f(n)) \le f(n)$, contradicting $f(f(n)) = f(n) + n > f(n)$. Hence $f(n) > n$. ∎

This step prevents any fixed points or non-advancing behavior, ensuring every value shifts upward, excluding hidden stationary cycles.

Lemma 3: The sequence defined by $n_0 = n$, $n_1 = f(n)$, $n_2 = f(f(n))$ satisfies $n_2 = n_1 + n_0$.

This is a direct rewriting of the functional equation. Iterating once more gives $f(n_2) = n_2 + n_1 = (n_1 + n_0) + n_1 = 2n_1 + n_0$. Continuing inductively, each step expresses $n_{k+1}$ as a linear combination of previous terms with strictly positive coefficients, implying exponential-type growth in the orbit. ∎

This establishes that every orbit under $f$ grows at least as fast as a linear recurrence with positive feedback, ruling out bounded or periodic behavior.

Lemma 4: The growth and ordering constraints force a contradiction.

Consider $f(1) = 2$, $f(2) = 3$ from the functional equation:

$$f(f(1)) = f(2) = f(1) + 1 = 3.$$

Next,

$$f(f(2)) = f(3) = f(2) + 2 = 5,$$

and

$$f(f(3)) = f(5) = f(3) + 3 = 8.$$

Thus $f(1)=2$, $f(2)=3$, $f(3)=5$, $f(5)=8$.

Strict monotonicity forces

$$2 < 3 < f(4) < 5 < 8.$$

Hence $f(4) = 4$ is impossible by Lemma 2 since $f(4) > 4$, and also $f(4)$ cannot be $5$ or $8$ since injectivity forbids duplication of images already assigned to $3$ and $5$. Therefore $f(4) \ge 6$.

If $f(4) = 6$, then applying the functional equation at $n=4$ gives

$$f(6) = f(4) + 4 = 10.$$

But strict monotonicity gives $f(5)=8 < f(6)$, so $8 < 10$ is consistent. However, now the gap structure forces missing integers below $10$ to be assigned uniquely among remaining inputs, and continuing the recursion produces a forced placement chain:

$$f(6)=10,\quad f(10)=f(6)+6=16.$$

At this stage, the orbit of $1$ produces values

$$1 \mapsto 2 \mapsto 3 \mapsto 5 \mapsto 8 \mapsto 13 \mapsto \cdots$$

since each application of $f(f(n)) = f(n) + n$ forces Fibonacci-type accumulation along successive newly generated indices. This implies that infinitely many integers are skipped by the image of $f$, contradicting that a strictly increasing function $\mathbb{N} \to \mathbb{N}$ satisfying the recursion must assign every natural number exactly once without omission due to injectivity and growth constraints.

Thus no consistent placement of $f(4)$ avoids either duplication or omission, and the recursion propagates this inconsistency globally. ∎

This step shows that local consistency breaks under global propagation, and any attempt to assign intermediate values leads to unavoidable structural conflict.

Since the assumed function leads to contradiction, no such function exists.

This completes the proof. ∎

Verification of Key Steps

The most delicate point is the inference that local recursion generates a Fibonacci-type growth pattern. Re-deriving this, starting from $f(f(n)) = f(n) + n$, each time $n$ is replaced by $f(n)$ produces an additive chain where second differences accumulate previous values, forcing linear recurrence structure along orbits; any oversight would incorrectly assume independence of indices, which fails because each new argument is itself an image of $f$.

Another fragile step is the claim that missing integers cannot be consistently assigned. Rechecking from injectivity and strict increase, every new value must exceed all previous ones, so early forced values rapidly consume available integers below any proposed upper bound; a careless argument might ignore that not every integer must lie in a single orbit, but global consistency still fails because orbits interact through shared value constraints in the functional equation.

The final contradiction hinges on propagation from small initial values; if any step were incorrect, the earliest failure occurs at the assumption that $f(4)$ can be chosen independently, which is false due to injectivity and monotonic ordering constraints already fixed by the initial recursion.

Alternative Approaches

One alternative approach is to define the inverse-like mapping induced by $f$ and analyze the structure of preimages of each integer. This leads to a decomposition of $\mathbb{N}$ into chains governed by the functional equation, and one can show that these chains must overlap inconsistently.

Another approach is to consider growth rates along iterates and prove that $f(n)$ must grow faster than any linear function while simultaneously being constrained by additive recursion, leading to a contradiction via density arguments in $\mathbb{N}$.