Functional Equations With Tricky Conditions

The two-step structure is mandatory: (1) derive what $f$ MUST be by substitutions that isolate a single value of $f$; (2) verify that the candidate actually satisfies the equation for all inputs — step (1) alone proves nothing, because it only used a few special cases of the hypothesis. Most lost points on USAMO functional equations are a missing verification or a missing "for all $x$" quantifier.

Iterated equations $f(f(x)) = g(x)$ hide two facts: injectivity of $f$ (if $g$ is injective), and the commutation $f(g(x)) = g(f(x))$ (apply $f$ to both sides). With monotonicity, the values between known ones are squeezed — $f(3) = 6$ and $f(6) = 9$ force $f(4) = 7$, $f(5) = 8$ — and the whole function unrolls. In base $3$ the $f(f(n)) = 3n$ solution is a digit rule; finding the pattern is not required, but proving the forced values is.

Recognize the order of the substitution map first — compose it with itself until it returns to $x$ — then write the cyclic system. The solution is a formula valid wherever all the substituted points are in the domain; say so. d'Alembert's equation $f(x+y) + f(x-y) = 2f(x)f(y)$ is the cosine/cosh addition law: $x=y=0$ gives $2f(0)=2f(0)^2$, so $f(0)\in\{0,1\}$; if $f(0)=0$ then $y=0$ gives $2f(x)=0$, so every solution other than $f\equiv0$ has $f(0)=1$, and then $x=y=1$ gives $f(2)=2f(1)^2-1$ with no regularity.

In $f(g(x,y))=y+h(x)$ the right side takes every real value as $y$ varies with $x$ fixed, so $f$ is surjective. And if $f(y_1)=f(y_2)$, replacing $y_1$ by $y_2$ inside $g$ leaves the left side unchanged, so $y_1+h(x)=y_2+h(x)$ and $y_1=y_2$ — injectivity, whenever $y$ enters $g$ only through $f(y)$. These two facts are the levers of most olympiad functional equations: surjectivity supplies a special input (the preimage of $0$), and injectivity turns an equation between values into an equation between arguments. Neither may be assumed; each must be derived from the equation before it is used.

Step 1 — $x=1$: $f(f(y)+1)=y+f(1)$. The right side takes every real value, so $f$ is surjective; and $f(y_1)=f(y_2)$ gives $y_1+f(1)=y_2+f(1)$, so $f$ is injective.

Step 2 — by surjectivity pick $t$ with $f(t)=-1$. Put $y=t$: $f(-x+x)=xt+f(x)$, i.e. $f(x)=f(0)-tx$ for every $x$. So $f$ is linear, $f(x)=a+bx$.

Step 3 — substitute: the left side is $a+bx(a+by+1)=a+(ab+b)x+b^2xy$, the right side $xy+a+bx$. Comparing coefficients, $b^2=1$ and $ab=0$, so $a=0$ and $b=\pm1$.

Step 4 — verify: $f(x)=x$ gives $xy+x=xy+x$; $f(x)=-x$ gives $f(-xy+x)=xy-x$ on both sides. The solutions are $f(x)=x$ and $f(x)=-x$.

How to find it. Setting $x=1$ isolates $y$ on the right, which yields surjectivity. The inner expression $xf(y)+x=x(f(y)+1)$ collapses to $0$ exactly when $f(y)=-1$, so the preimage of $-1$ is the special value to use.

Step 1 — $x=0$: $f(f(y))=y+c^2$ with $c=f(0)$. The right side is a bijection of $y$, so $f$ is injective and surjective.

Step 2 — replacing $x$ by $-x$ leaves the left side unchanged, so $f(-x)^2=f(x)^2$. Take $a$ with $f(a)=0$: then $f(-a)^2=0$, so $f(-a)=0=f(a)$ and injectivity gives $a=-a$, $a=0$. Hence $c=f(0)=0$ and $f(f(y))=y$.

Step 3 — $y=0$: $f(x^2)=f(x)^2\ge0$, so $f\ge0$ on $[0,\infty)$.

Step 4 — additivity: for $s\ge0$ write $s=x^2$; using $y=f(f(y))$,

With $y=-s$ this gives $f(-s)=-f(s)$, and then $f(y-s)=f(y)-f(s)$ follows from the displayed line applied to $y-s$; so $f(u+v)=f(u)+f(v)$ for all reals.

Step 5 — an additive function that is $\ge0$ on $[0,\infty)$ is increasing ($u\le v\Rightarrow f(v)-f(u)=f(v-u)\ge0$), and an increasing additive function is $f(x)=kx$. From $f(f(x))=x$, $k^2=1$, and $f\ge0$ on positives gives $k=1$.

Step 6 — $f(x)=x$ satisfies the equation: $x^2+y=y+x^2$.

How to find it. $x=0$ turns the equation into $f\circ f=$ a shift, giving bijectivity at once. The symmetry $x\mapsto-x$ plus injectivity pins the zero of $f$; the square $f(x^2)=f(x)^2$ supplies the sign condition that replaces continuity in Cauchy's equation.

Cancelling needs injectivity, and nothing in the equation provides it. The constant $f\equiv0$, the function $f(x)=|x|$, and indeed any $f$ that fixes every point of its own image ($f(x)=\lfloor x\rfloor$, for one) all satisfy $f(f(x))=f(x)$. The equation says exactly "$f$ is the identity on its image", and the image can be any set. Before cancelling $f$ from $f(A)=f(B)$, point to the line of your solution where injectivity was proved.

For additive $f$, $f(x+x+\cdots+x)=f(x)+\cdots+f(x)$ gives $f(nx)=nf(x)$ for positive integers $n$; $f(0)=f(0+0)=2f(0)$ gives $f(0)=0$ and then $f(-x)=-f(x)$. Applying $f(nx)=nf(x)$ with $x=\tfrac1n$ gives $f(\tfrac1n)=\tfrac1nf(1)$, and so $f(\tfrac mn)=\tfrac mnf(1)$. On $\mathbb R$ the same argument reaches only the rationals; passing to irrationals needs a limit, which is where continuity or monotonicity enters. On a discrete domain every value is reached by finitely many steps from a few starting values, so induction does the whole job — and the discreteness itself (integer values, gaps of at least $1$) often replaces the missing analysis.

Step 1 — $m=0$: $f(f(n))=f(0)+n$, so $f$ is a bijection of $\mathbb Z$.

Step 2 — take $a$ with $f(a)=0$ and put $n=a$: $f(m)=f(m)+a$, so $a=0$. Hence $f(0)=0$ and $f(f(n))=n$.

Step 3 — the equation now reads $f(m+f(n))=f(m)+f(f(n))$; since $f(n)$ runs over all of $\mathbb Z$, $f(m+k)=f(m)+f(k)$ for all integers $m,k$.

Step 4 — additive on $\mathbb Z$ means $f(n)=cn$ with $c=f(1)$, and $f(f(1))=c^2=1$ gives $c=\pm1$.

Step 5 — both work: $f(n)=n$ gives $m+n$ on each side, $f(n)=-n$ gives $-m+n$ on each side.

How to find it. $m=0$ yields bijectivity, the preimage of $0$ yields $f(0)=0$, and then the equation is literally Cauchy's with one argument written as $f(n)$. On $\mathbb Z$ Cauchy's equation has only linear solutions, so no regularity is needed — the same equation on $\mathbb R$ would admit wild additive involutions.

Step 1 — claim: for every $k\ge1$, $f(n)\ge k$ whenever $n\ge k$. For $k=1$ this is $f(n)\ge1$. Suppose it holds for $k$ and let $n\ge k+1$. Then $n-1\ge k$, so $f(n-1)\ge k$, and applying the claim to the number $f(n-1)\ge k$ gives $f(f(n-1))\ge k$. The hypothesis then gives $f(n)>f(f(n-1))\ge k$, so $f(n)\ge k+1$.

Step 2 — taking $k=n$: $f(n)\ge n$ for all $n$.

Step 3 — so $f(n+1)>f(f(n))\ge f(n)$: $f$ is strictly increasing.

Step 4 — strictly increasing means $a<b\iff f(a)<f(b)$. The hypothesis $f(f(n))<f(n+1)$ therefore gives $f(n)<n+1$, i.e. $f(n)\le n$. With Step 2, $f(n)=n$.

How to find it. The inequality compares $f$ at two points, one of which is a value of $f$ — useless until you know how $f$ compares with the identity. The induction on $k$ bootstraps "$f(n)\ge$ something" from $f(n)\ge1$; once $f\ge\mathrm{id}$ is known, monotonicity follows and the hypothesis can be read backwards.

Step 1 — $f$ is injective (equal values give equal $n+1987$), and applying $f$ to both sides of the hypothesis at $f(n)$ gives $f(n+1987)=f(f(f(n)))=f(n)+1987$. So $f(n)\bmod1987$ depends only on $n\bmod1987$, and $f$ induces a map $g$ on the residues $\{0,1,\dots,1986\}$ with $g(g(r))=r+1987\equiv r$.

Step 2 — for a residue $r$ write $f(r)=r'+1987k$ with $0\le r'<1987$, $k\ge0$, and $f(r')=r''+1987j$. Then $f(f(r))=f(r')+1987k=r''+1987(j+k)$, which must equal $r+1987$. So $r''=r$ and $j+k=1$: exactly one of $k,j$ is $1$.

Step 3 — $g$ has no fixed point: if $r'=r$, then $j=k$ and $2k=1$, impossible.

Step 4 — so $g$ is an involution on a set of $1987$ elements without fixed points, splitting it into pairs $\{r,g(r)\}$. That needs an even number of elements, but $1987$ is odd. Contradiction.

How to find it. $f\circ f$ commuting with the shift makes $f$ commute with it too, so $f$ descends to residues mod $1987$, where $f\circ f$ is the identity. An involution without fixed points pairs things up — a parity argument. With $4$ in place of $1987$ (the equation $f(f(n))=n+4$) solutions exist, because $4$ is even.

The substitution $\log f(e^u)$ needs $f$ defined on the reals $e^u$, but here the domain is $\mathbb Q_{>0}$, whose multiplicative structure is not that of $\mathbb Q$: it is free on the primes. Any assignment of values to the primes extends to a multiplicative $f$. Swap $2$ and $3$: $f(2)=3$, $f(3)=2$, $f(p)=p$ for other primes, extended by $f\left(\prod p^{e_p}\right)=\prod f(p)^{e_p}$. Then $f(6)=6$ but $f(4)=9$, so no single exponent $c$ works. On $\mathbb Q_{>0}$ (or $\mathbb N$), a multiplicative equation says "choose $f$ on the primes", and the rest of the problem must pin those choices down.