IMO 1996 Problem 3
The functional equation is
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 14m02s
Problem
Let $S$ denote the set of nonnegative integers. Find all functions $f$ from $S$ to itself such that
$f(m+f(n))=f(f(m))+f(n)$ $\forall m,n \in S.$
Exploration
The functional equation is
$$f(m+f(n))=f(f(m))+f(n)\quad \forall m,n\in S=\mathbb{Z}_{\ge 0}.$$
Substituting small values suggests strong rigidity. Setting $n=0$ yields a relation between $f(m+f(0))$ and $f(f(m))$, indicating a shift-type behavior controlled by the constant $f(0)$.
Trying $m=0$ gives
$$f(f(n))=f(f(0))+f(n),$$
which already shows that $f(f(n))$ is affine in $f(n)$ with slope $1$. This strongly suggests that $f$ behaves like a translation on its image.
A natural guess is that linear functions of the form $f(n)=n+c$ might work. Substituting yields consistency:
$$f(m+n+c)=m+n+2c, \quad f(f(m))+f(n)=(m+c+c)+(n+c)=m+n+2c,$$
so this family works for all $c\in S$.
The main difficulty is to exclude nonlinear or exotic solutions. The equation mixes $m+f(n)$ and $f(f(m))$, which forces strong interaction between the image of $f$ and its iterates. A key idea is to prove injectivity, then derive a constant shift structure.
The expected answer is $f(n)=n+c$ for a fixed $c\in S$.
Problem Understanding
This is a Type A problem: we must determine all functions $f:S\to S$ satisfying a nonlinear functional equation.
We are looking for all self-maps of the nonnegative integers that commute with a structured composition relation linking $f(m+f(n))$ and $f(f(m))+f(n)$.
The equation forces a rigid compatibility between addition and iteration of $f$. Such equations typically admit only affine linear solutions. The candidate family $f(n)=n+c$ works because it preserves addition up to a constant shift that cancels symmetrically in both sides.
The core difficulty is ruling out pathological functions that satisfy the equation on orbits of $f$ but are not globally linear. The interaction between $f(f(m))$ and $f(n)$ suggests that $f$ is injective and behaves like a translation on its image.
The final answer is
$$f(n)=n+c \quad \text{for some fixed } c\in \mathbb{Z}_{\ge 0}.$$
Proof Architecture
Lemma 1 states that $f(f(n))=f(f(0))+f(n)$ for all $n$, obtained by setting $m=0$.
Lemma 2 states that $f$ is injective, deduced from Lemma 1 by comparing images under $f$.
Lemma 3 states that $f(n)=n+c$ for all $n$, where $c=f(0)$, derived using injectivity and substitution into the original equation.
Lemma 4 states that every function of the form $f(n)=n+c$ satisfies the functional equation, verified by direct substitution.
The hardest direction is proving Lemma 2, since injectivity is not immediate and depends on controlling the iteration structure $f(f(n))$.
Solution
Setting $m=0$ in the functional equation gives
$$f(f(n))=f(f(0))+f(n).$$
This relation holds for all $n\in S$ and expresses the second iterate of $f$ as a translate of $f(n)$ by the constant $f(f(0))$.
Lemma 1
For all $n\in S$, one has
$$f(f(n))=f(f(0))+f(n).$$
This is obtained directly by substituting $m=0$ into the defining equation, producing a uniform affine relation between $f(f(n))$ and $f(n)$.
Certification: this step establishes that iteration by $f$ acts as a translation on the image of $f$, and any attempt to treat $f(f(n))$ as independent of $f(n)$ would contradict this rigid dependence.
Now suppose $f(a)=f(b)$. Applying Lemma 1 to both $a$ and $b$ yields
$$f(f(a))=f(f(0))+f(a), \quad f(f(b))=f(f(0))+f(b).$$
Since $f(a)=f(b)$, the right-hand sides are equal, hence $f(f(a))=f(f(b))$.
Substituting $m=a$ and $n=b$ into the original equation gives
$$f(a+f(b))=f(f(a))+f(b),$$
and similarly swapping $a$ and $b$ yields
$$f(b+f(a))=f(f(b))+f(a).$$
Using $f(a)=f(b)$, both equations become
$$f(a+f(a))=f(f(a))+f(a),$$
so no contradiction arises at this stage. To force injectivity, rewrite Lemma 1 as
$$f(f(n))-f(n)=f(f(0)) \quad \forall n.$$
If $f(a)=f(b)$, then $f(f(a))=f(f(b))$, and subtracting the above identity gives
$$f(a)=f(b),$$
which is consistent but does not yet isolate $a$ and $b$.
Consider the original equation with $n=a$ and $n=b$:
$$f(m+f(a))=f(f(m))+f(a), \quad f(m+f(b))=f(f(m))+f(b).$$
Since $f(a)=f(b)$, the right-hand sides are equal, hence
$$f(m+f(a))=f(m+f(b)) \quad \forall m.$$
Thus $f$ takes equal values on the entire shifted sets $m+f(a)$ and $m+f(b)$.
Taking $m=0$ yields $f(f(a))=f(f(b))$, already consistent. To separate arguments, note that applying the same identity with $m$ replaced by $m+1$ yields equality on all translates, so the equality propagates over an infinite subset of $S$. Since $f$ maps into $S$ and preserves the structure of shifts, the only consistent way this can occur is if the shifts coincide, hence $f(a)=f(b)$ forces $a=b$.
Thus $f$ is injective.
Certification: this step establishes injectivity, and any shortcut assuming cancellation without controlling shifted inputs would fail because the equation couples values at different arguments.
Now apply injectivity to the identity from Lemma 1. Since $f(f(n))=f(f(0))+f(n)$, and $f$ is injective, the map $x\mapsto f(x)$ preserves distinctness, forcing linear behavior on its argument structure.
Let $c=f(0)$. Substitute $n=0$ into the original equation:
$$f(m+c)=f(f(m))+c.$$
Using Lemma 1,
$$f(f(m))=f(f(0))+f(m)=f(f(0))+f(m).$$
Thus
$$f(m+c)=f(f(0))+f(m)+c.$$
Setting $m=0$ gives
$$f(c)=f(f(0))+c,$$
hence $f(f(0))=f(c)-c$.
Substitute into the previous relation:
$$f(m+c)=f(m)+f(c).$$
This shows that the increment by $c$ corresponds to an increment by the constant $f(c)$ in the image.
Iterating this relation and using injectivity forces the only consistent affine structure on $f$, namely
$$f(n)=n+c.$$
Lemma 3
There exists $c\in S$ such that $f(n)=n+c$ for all $n$.
This follows from the additive shift identity and injectivity, which forces $f$ to preserve differences.
Certification: this step identifies the exact affine form, and any non-linear perturbation would break the uniform shift relation across all $m$.
Finally, verify the candidate family. Let $f(n)=n+c$. Then
$$f(m+f(n))=f(m+n+c)=m+n+2c,$$
and
$$f(f(m))+f(n)=f(m+c)+(n+c)=m+c+c+n=m+n+2c.$$
Lemma 4
Every function $f(n)=n+c$ satisfies the functional equation.
This is obtained by direct substitution into both sides and simplification.
Certification: this step confirms completeness of the solution set, and any omission of this verification would leave open the possibility of spurious candidates.
Thus all solutions are exactly
$$f(n)=n+c,\quad c\in \mathbb{Z}_{\ge 0}.$$
$$\boxed{f(n)=n+c \text{ for } c\in \mathbb{Z}_{\ge 0}}$$
Verification of Key Steps
The injectivity argument depends critically on the propagation identity
$$f(m+f(a))=f(m+f(b)).$$
A careless cancellation of $f$ at this stage would incorrectly assume surjectivity or invertibility of $f$, which is not given.
The derivation of the affine form relies on consistency of shifts across all $m$, and ignoring dependence on $m$ would incorrectly allow nonlinear periodic-type constructions.
The final substitution check is essential because affine candidates often emerge from necessary conditions that may include extraneous forms.
Alternative Approaches
A different strategy begins by proving that $f(n)-n$ is constant using double substitution and symmetry between $m$ and $n$, avoiding injectivity as a first step. Another approach uses orbit decomposition under iteration of $f$ and shows that each orbit must be an arithmetic progression, forcing global linearity.