Functional Equations

1. Introduction

A functional equation is an equation whose unknown is a function rather than a number. It asserts that some identity involving $f$ holds for all inputs in a given domain — for example, $f(x + y) = f(x) + f(y)$ for all real $x, y$ — and the task is to find every function $f$ that satisfies it. This shifts the mindset from "solve for $x$" to "characterize all $f$", and it rewards systematic experimentation.

Functional equations are a flagship olympiad topic and a recurring AIME theme (often in the guise of a sequence or a recurrence). They reward a small set of reusable maneuvers: substituting clever values, comparing the equation to itself with variables swapped, deducing structural properties like injectivity or surjectivity, and proving that a guessed family of solutions is the only one. The discipline is twofold — you must find candidate solutions and prove there are no others.

This article presents the standard playbook: the substitution method, the theory of Cauchy's functional equation and its cousins (Jensen, multiplicative, exponential), techniques for establishing injectivity/surjectivity, fixed points, and the all-important final verification step. We work a series of increasingly difficult problems with complete solutions, emphasizing both the discovery process and the rigor needed to claim a complete answer.

AIME vs olympiad. AIME functional-equation problems usually ask for a specific value ($f(5)$, $f(10)$) rather than the full solution set. You may find the answer by bootstrapping from $P(1,1)$, $P(2,1)$, etc., without a complete uniqueness proof — but verify your candidate satisfies the original equation. Olympiad problems require the full characterization with proof.

The $P(x,y)$ discipline. Label every substitution. This prevents circular reasoning and makes it easy to spot which values of $x, y$ have not yet been tried. A systematic sweep of $P(0,0)$, $P(x,0)$, $P(0,y)$, $P(x,x)$, $P(x,-x)$ resolves most contest equations.

2. Core Concepts

2.1 What Counts as a Solution

To "solve" a functional equation means to describe the entire solution set. A complete answer has two parts: (1) existence/verification — exhibit functions and check they satisfy the equation; and (2) uniqueness/completeness — prove no other function works. Skipping part (2) is the most common way to lose credit; finding $f(x) = cx$ works is not the same as proving nothing else does.

2.2 The Substitution Method

The primary tool is plugging in well-chosen values. Useful first moves:

• $x = y = 0$ to find $f(0)$.
• $y = 0$ or $x = 0$ to relate $f$ at a point to a constant.
• $y = x$ to expose doubling or squaring structure.
• Swapping $x \leftrightarrow y$ and comparing, to exploit or break symmetry.
• Substituting an expression (like $y \to -x$ or $y \to \frac{1}{x}$) to create cancellations.

Let $P(x, y)$ denote the assertion of the equation for specific inputs; competition write-ups often abbreviate "substitute $x = a, y = b$" as "$P(a, b)$".

2.3 Cauchy's Functional Equation

The additive Cauchy equation is $f(x + y) = f(x) + f(y) \quad \text{for all } x, y.$ Over the rationals, the only solutions are $f(x) = cx$ where $c = f(1)$: setting $y = x$ gives $f(2x) = 2f(x)$, induction gives $f(nx) = nf(x)$, and a short argument extends this to all rationals. Over the reals, $f(x) = cx$ are the only solutions provided a mild regularity condition holds — any one of: continuity at a point, monotonicity, boundedness on an interval, or measurability. Without such a condition, pathological (non-measurable) solutions exist via a Hamel basis, but these never arise in well-posed contest problems.

2.4 Related Standard Equations

• Jensen: $f\!\left(\frac{x+y}{2}\right) = \frac{f(x) + f(y)}{2}$ leads to affine solutions $f(x) = cx + d$ (with regularity).
• Multiplicative: $f(xy) = f(x)f(y)$ typically gives power solutions $f(x) = x^c$ on $\mathbb{R}^+$ (with regularity), plus the trivial $f \equiv 0$.
• Exponential (Cauchy's other equation): $f(x + y) = f(x)f(y)$ gives $f(x) = a^x$ (or $f \equiv 0$).
• Logarithmic: $f(xy) = f(x) + f(y)$ gives $f(x) = c\ln x$ on $\mathbb{R}^+$. These are often reached by transforming a given equation into Cauchy form via a substitution like $g = \ln f$ or $g(x) = f(e^x)$.

2.5 Injectivity, Surjectivity, and Fixed Points

Deducing structural properties from the equation is a powerful uniqueness tool:

• Injectivity: if you can manipulate the equation into "$f(a) = f(b) \Rightarrow a = b$", you may cancel $f$ from both sides.
• Surjectivity: if $f$ hits every value, you can substitute "let $f(t) = c$" for an arbitrary $c$, unlocking new substitutions.
• Fixed points: values with $f(a) = a$ often propagate (e.g. if $a, b$ are fixed points, so might be $a + b$ or $ab$), constraining $f$.

2.6 The $P(x,y)$ Notation and Systematic Casework

Write $P(x, y)$ for the assertion of the equation. A disciplined solver records each substitution as $P(a, b)$ and tracks what each yields. When $f(0)$ branches into cases ($0$ vs $1$ vs other), handle each branch completely before merging conclusions.

2.7 Extending from $\mathbb{Q}$ to $\mathbb{R}$

The standard extension argument: from $f(x+y) = f(x)+f(y)$, prove $f(nx) = nf(x)$ for integers $n$, then $f(p/q) = (p/q)f(1)$ for rationals. Continuity (or monotonicity) then extends $f(q) = cq$ from dense $\mathbb{Q}$ to all $\mathbb{R}$. On the AIME, you often only need values at integers or rationals.

2.8 Involutions and Bijections

If $f(f(x)) = x$ for all $x$, then $f$ is a bijection and equals its own inverse. Combined with Cauchy-type structure, this often forces $f(x) = x$ or $f(x) = -x$. The involution $f(x) = 1/x$ on $\mathbb{R}^+$ is another standard example.

2.9 Polynomial and Quadratic Templates

The parallelogram law $f(x+y) + f(x-y) = 2f(x) + 2f(y)$ (Jensen's quadratic equation) has even solutions $f(x) = kx^2$ (with continuity). The Cauchy–Euler template $f(xy) = xf(y) + yf(x)$ on $\mathbb{R}^+$ suggests $f(x) = cx \ln x$ after differentiation or substitution $g(x) = f(x)/x$.

2.10 Iteration and Orbit Analysis

For $f(f(x)) = g(x)$, iterating $f$ produces an orbit $x, f(x), f(f(x)), \ldots$. If the orbit is finite or enters a cycle, strong constraints emerge. Fixed points of $f$ are seeds for orbit analysis.

2.11 Symmetry and Odd/Even Decomposition

Write $f(x) = f_{\text{even}}(x) + f_{\text{odd}}(x)$ where $f_{\text{even}}(x) = \frac{f(x)+f(-x)}{2}$ and $f_{\text{odd}}(x) = \frac{f(x)-f(-x)}{2}$. If the equation is even in $x$, the odd part may vanish, reducing the problem.

2.12 Substitution $g(x) = f(x) - x$ or $g(x) = f(x) - c$

Shifting $f$ by a constant or by the identity often eliminates lower-order terms. If $f(x+y) = f(x) + f(y) + xy$, set $g(x) = f(x) - \frac{x^2}{2}$ to reach Cauchy.

2.13 Recurrence from Special Values

Setting $y = 1$ in $f(xy) = f(x)f(y)$ gives $f(x) = f(x)f(1)$, so either $f \equiv 0$ or $f(1) = 1$. One special value often cascades into a full determination via induction.

2.14 Verification and Domain Restrictions

Every proposed solution must be checked in the original equation on the stated domain. A function that works on $\mathbb{R}^+$ may fail on $\mathbb{R}$ if $f(0)$ is undefined or inconsistent. State regularity assumptions explicitly.