Functional Equations With Tricky Conditions

Study Sheet

Functional Equations With Tricky Conditions

Substitutions that isolate f, injectivity from the equation, monotone f(f(n)) = 3n, Möbius orders, d'Alembert

Pinning Down the Function

Tip
Substitute to isolate, then verify

f(x2+y)=f(x)2+yf(x^2 + y) = f(x)^2 + y: replace yy by y−x2y - x^2 to get f(y)=y+cf(y) = y + c, then substitute back to force c=0c = 0. f(x)f(y)−f(xy)=x+yf(x)f(y) - f(xy) = x + y: y=0y = 0 gives f(x)=x+1f(x) = x + 1 once f(0)=1f(0) = 1 is forced.

The two-step structure is mandatory: (1) derive what ff MUST be by substitutions that isolate a single value of ff; (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 xx" quantifier.

Tip
Injectivity, surjectivity, and iteration

From f(f(n))=n+4f(f(n)) = n + 4: ff is injective (compose the hypothesis), and applying ff once more gives f(n+4)=f(n)+4f(n + 4) = f(n) + 4, so ff is determined by four values. From strictly increasing ff with f(f(n))=3nf(f(n)) = 3n: f(1)=2f(1) = 2 is forced, and the values propagate upward.

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

Tip
Möbius substitutions and cyclic systems

If g(x)=11−xg(x) = \tfrac{1}{1-x} then g3=idg^3 = \mathrm{id}: an equation f(x)+f(g(x))=xf(x) + f(g(x)) = x yields three linear equations in f(x),f(gx),f(g2x)f(x), f(gx), f(g^2x), solved by adding and subtracting. Involutions (g2=idg^2 = \mathrm{id}, like x↦1xx \mapsto \tfrac1x or x+1x−1\tfrac{x+1}{x-1}) give two equations.

Recognize the order of the substitution map first — compose it with itself until it returns to xx — 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)f(x+y) + f(x-y) = 2f(x)f(y) is the cosine/cosh addition law: x=y=0x = y = 0 pins f(0)=1f(0) = 1, and f(2)=2f(1)2−1f(2) = 2f(1)^2 - 1 follows with no regularity.

Side note
Regularity: when you need it and when you don't

Cauchy's f(x+y)=f(x)+f(y)f(x+y) = f(x) + f(y) is linear on Q\mathbb Q unconditionally, and on R\mathbb R only with continuity, monotonicity, or boundedness on an interval. If a problem gives no regularity, either the answer is a specific value that follows from finitely many substitutions (most USAMO problems), or the domain is N\mathbb N/Q\mathbb Q/Z\mathbb Z where induction replaces continuity. Never assume continuity silently.

Try it
Try it: a forced value

f:R→Rf:\mathbb R\to\mathbb R with f(x+y)=f(x)+f(y)+2xyf(x + y) = f(x) + f(y) + 2xy and f(1)=3f(1) = 3. Find f(4)f(4).

g(x)=f(x)−x2g(x) = f(x) - x^2 is additive, g(1)=2g(1) = 2, so g(4)=8g(4) = 8 and f(4)=8+16=24f(4) = 8 + 16 = 24. Verify: f(x)=x2+2xf(x) = x^2 + 2x satisfies the equation ✓.