Lemma › Guides › Cauchy's functional equation in olympiad problems: what you need
Guide

Cauchy's functional equation in olympiad problems: what you need

Cauchy's functional equation is f(x+y)=f(x)+f(y)f(x+y) = f(x) + f(y). It looks like it should have one family of solutions, f(x)=cxf(x) = cx, and it does, as long as you add one more condition. That condition is the thing people forget, and it is the thing contest problems are built around.

What is true

Suppose f:R→Rf : \mathbb{R} \to \mathbb{R} satisfies f(x+y)=f(x)+f(y)f(x+y) = f(x) + f(y) for all real x,yx, y.

Without any other assumption you can prove that f(q)=qf(1)f(q) = qf(1) for every rational qq. That is all. On the reals there are other solutions, wild ones that are not of the form cxcx. They can only be constructed using the axiom of choice, and their graphs are dense in the plane. A contest will never ask you to build one, but it will make you prove that none exist under a stated condition, so you cannot skip the extra hypothesis.

Any one of these extra conditions is enough to force f(x)=cxf(x) = cx on all of R\mathbb{R}:

The rational part

Everything starts with the two obvious substitutions. Put x=y=0x = y = 0 to get f(0)=0f(0) = 0. Put y=−xy = -x to get f(−x)=−f(x)f(-x) = -f(x), so ff is odd. These are the usual moves from symmetry: swap the roles or cancel a pair.

Then, by induction on nn, f(nx)=nf(x)f(nx) = nf(x) for every positive integer nn and every real xx. Take x=1/nx = 1/n: n f(1/n)=f(1)n\,f(1/n) = f(1), so f(1/n)=f(1)/nf(1/n) = f(1)/n. Now f(m/n)=f(m⋅1n)=m f(1n)f(m/n) = f(m \cdot \tfrac1n) = m\,f(\tfrac1n), and by the previous step that is m f(1)/nm\,f(1)/n. With oddness this covers every rational. If f(1)=cf(1) = c, then f(q)=cqf(q) = cq for rational qq.

The step to the reals

Say ff is increasing. Then c=f(1)≥f(0)=0c = f(1) \ge f(0) = 0. For a real xx and a whole number nn, let p=⌊nx⌋p = \lfloor nx \rfloor, so that p/n≤x≤(p+1)/np/n \le x \le (p+1)/n. Monotonicity gives

c pn  ≤  f(x)  ≤  c p+1n.c\,\frac{p}{n} \;\le\; f(x) \;\le\; c\,\frac{p+1}{n}.

The width of the interval is c/nc/n. Let nn grow, and f(x)f(x) is trapped at cxcx.

To see this with numbers, take c=3c = 3 and x=2x = \sqrt2. Use n=1000n = 1000: 1.414≤2≤1.4151.414 \le \sqrt2 \le 1.415, so 4.242≤f(2)≤4.2454.242 \le f(\sqrt2) \le 4.245. The true value is 32≈4.24263\sqrt2 \approx 4.2426. Use n=100000n = 100000 and the interval has width 0.000030.00003.

Example: a non-negativity condition

Find all additive ff with f(x)≥0f(x) \ge 0 for every x≥0x \ge 0.

If x≥yx \ge y then f(x)−f(y)=f(x−y)≥0f(x) - f(y) = f(x - y) \ge 0, so ff is increasing. By the squeeze, f(x)=cxf(x) = cx with c=f(1)≥0c = f(1) \ge 0. Every such function works: c(x+y)=cx+cyc(x+y) = cx + cy and cx≥0cx \ge 0 for x≥0x \ge 0.

Example: additive and multiplicative

Find all f:R→Rf : \mathbb{R} \to \mathbb{R} with f(x+y)=f(x)+f(y)f(x+y) = f(x) + f(y) and f(xy)=f(x)f(y)f(xy) = f(x)f(y).

Put y=xy = x in the second condition: f(x2)=f(x)2≥0f(x^2) = f(x)^2 \ge 0. Every non-negative real is a square, so f(t)≥0f(t) \ge 0 for all t≥0t \ge 0. That is the previous example, so f(x)=cxf(x) = cx. Now the second condition at x=y=1x = y = 1 says c=c2c = c^2. So c=0c = 0 or c=1c = 1, and both functions satisfy both conditions.

Notice how the second condition did the work. Without the multiplicative condition you could not rule out a wild solution.

Example: Cauchy in disguise

Find all continuous ff with f(x+y)=f(x)+f(y)+2xyf(x+y) = f(x) + f(y) + 2xy.

The extra term 2xy2xy is what x2x^2 produces: (x+y)2=x2+y2+2xy(x+y)^2 = x^2 + y^2 + 2xy. So set g(x)=f(x)−x2g(x) = f(x) - x^2. Then

g(x+y)=f(x+y)−(x+y)2=f(x)+f(y)+2xy−x2−2xy−y2=g(x)+g(y).g(x+y) = f(x+y) - (x+y)^2 = f(x) + f(y) + 2xy - x^2 - 2xy - y^2 = g(x) + g(y).

The function gg is additive and continuous, so g(x)=cxg(x) = cx, and f(x)=x2+cxf(x) = x^2 + cx.

Learn that move first. When the right side of a functional equation has Cauchy's shape plus an extra term, guess a polynomial that creates the extra term and subtract it.

Where it goes wrong

What to do with this

Before you start a functional equation, ask which form it takes after the easy substitutions. If you reach f(x+y)=f(x)+f(y)f(x+y) = f(x) + f(y), list every condition in the problem and ask which of them gives regularity. If none does, the problem is probably over the rationals. The guide on starting a functional equation covers the substitutions that get you to this point. The symmetry technique page has the swap-and-cancel moves, and the problem archive has more functional equations to practise on.

Related guides

Techniques in this guide

Competitions this guide helps with

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level