FuncEq Intronnnnnnnnnnnnnn
FuncEq Intronnnnnnnnnnnnnn
FuncEq Intronnnnnnnnnnnnnn
Evan Chen
So have you ever played three-player bughouse chess and been on the middle board?
Basically, a very effective strategy is to just throw down pieces seemingly at random
until you get something that works literally, just try the first thing that comes to
mind. Other times, if this isnt working and youre running low on pieces (and are being
told to stop singing by certain people), then you have to make use of what youve got and
do something fancier, but this is rare. Usually just slamming stuff on the board works,
especially against weak opponents.
This is all a metaphor.
Max Schindler
Let f : A B be a function. The set A is called the domain, and B the codomain.
A couple definitions which will be useful:
In this handout, by solve over K I will mean find all functions f : K K such
that the equation holds for all inputs in K.
Acknowledgments
Thanks to Ashwin Sah and David Stoner for detailed suggestions, and to Ryan Kim,
Kevin Qian and Franklyn Wang for comments and corrections.
1 Synopsis
A typical functional equation will ask you to find all functions satisfying so-and-so
property, for example:
1
Evan Chen (October 18, 2016) 2 First Example
check that all objects satisfying the condition are of the form you describe
and prove that anything of the form you describe satisfies the condition.
In the context of this problem, this means you need to show that
f (x2 y 2 ) = xf (x) yf (y) if and only if f (x) = kx.
Of course the if direction is trivial in this example, and the bulk of the work is only
if. However, you should keep clear in your mind both directions, and also remember to
state that the if direction is trivial on a contest, or you will lose a point!
Solution. The answer is f (x) = kx, k R. Its easy to see that these functions
satisfy the given equation.
We now show these are the only solutions. . .
2 First Example
For concreteness, let me start off with a standard example, that shows a lot of the types
of things that often come up in these sorts of problems.
for all x, y R.
Solution. Before I begin solving the problem, can you guess what the answer is? Clearly,
f (x) = +x works. But theres actually a second solution: f (x) = x. In general, a
garden-variety functional equation will have f (x) = x as a solution, but sometimes also
f (x) = 0, f (x) = kx, f (x) = x + c, or even f (x) = kx + c. So therefore, I recommend
at the start of every problem that you start by seeing which if any of these
functions are solutions, and to just keep these in your head.1
1
One reader suggests also checking degree n polynomials in general. This is often easier than it seems,
since degrees usually end up not matching except for finitely many n.
2
Evan Chen (October 18, 2016) 2 First Example
For this problem, it looks like f (x) = x is a solution, so we just need to keep in mind
that we need to allow for this case.
Now, where do we begin? Well, one can simply start off by plugging stuff in, and
grabbing whatever low-hanging fruit we can. Usually, the first thing I try is setting all
zeros; this is often helpful, and in general your first attempts should try to make a lot of
terms vanish. When we do this here, we get
f (f (0)2 + f (0)) = 0.
The inner term is pretty messy, but let me for now just denote it u, i.e. we have some u
such that f (u) = 0. This is still useful, because we can use it to make things disappear!
By plugging in x = u we obtain that
f (f (y)) = y.
3
Evan Chen (October 18, 2016) 3 Cauchys Functional Equation Over Q
Remark 2.4. There are of course other approaches. Here is an outline of another one.
After showing f is an involution, one can simultaneously let x = f (t), y = f (u) and
instead obtain
f (t2 + u) = tf (t) + f (u)
(check this!). This quickly becomes a Cauchy equation, see below and Problem 8.3.
Remark 2.5. Possibly helpful suggestion: the set of solutions you find also motivates
which claims may be helpful to prove. For example, if f (x) = x and f (x) = 2 x then
you cant hope to prove f (0) = 0 or f (xy) = f (x)f (y), but it may be possible to show
f (1) = 1 or f involutive, for example.
Solution. As before we begin by examining which functions we think the answers are.
Trying out the most general f (x) = kx + c, we find that c = 0 but k can be anything. So
our guess is that the answer is f (x) = kx.
We now prove this guess is right. First of all, all such functions clearly work.
Now, to actually solve the problem, observe that we have one degree of freedom: the
family of solutions has a free variable. So it makes sense to set, say, k = f (1) and try to
solve everything else in terms of k.
We begin now by setting x = y = 0 to derive f (0) = 0. Then, we can put x = 1, y = 1
to get f (2) = f (1) + f (1) = 2k. Now, (x, y) = (2, 1) gives f (3) = 3k, and so on, so by
induction we get f (n) = kn for any integer n 1.
What about the negative integers? Well, by putting x = y we get f (x) + f (x) = 0,
and so in fact f is odd. Thus the result f (n) = kn holds for the negative integers.
Were still stuck with the problem of getting all of Q. As a thought experiment, lets
see what we can do to get f ( 12 ). We have that
1 1
f +f = f (1) = k
2 2
whence f ( 12 ) = 12 k. And now the path is clear for general p/q: we have
and hence f (p/q) = k p/q. Thus, we conclude that f (x) = kx for all x.
Remark 3.2. Notice how the choice of Q as domain is critical: this all works out because
we are able to do induction in order to get the function f over Z inputs, and then over
Q. This fails if f : R Q, as the next section shows.
In contrast, the choice of codomain is irrelevant, we run into no problem if we repeat
this proof for f : Q R.
4
Evan Chen (October 18, 2016) 3 Cauchys Functional Equation Over Q
Solution. This time, our preliminary checks reveal that f (x) = kx + c works for any k
and c. (In a vague sense, the fact that c is free to vary is manifested in the fact that
plugging in all zeros yields the tautology 0 = 0.) So now we do the following trick: we
can shift the function f by c without changing the function. To be clear, this means that
we rewrite the given as
x+y
(f (x) f (0)) + (f (y) f (0)) = 2 f f (0) .
2
If we now let g(x) = f (x) f (0), then we derive
x+y
g(x) + g(y) = 2g
2
so this is the same functional equation but now, we know g(0) = 0.
So, setting (x, y) = (t, 0) gives g(t) = 2g(t/2). We might try the same trick as before
with Cauchy, say setting (x, y) = (1, 2) to get
g(1) + g(2) = 2g(3/2)
which seems non-useful until we remember we have g(t) = 2g(t/2). Indeed, the given
functional equation can be rewritten as
x+y
g(x) + g(y) = 2g = g (x + y)
2
with t = x + y. So g satisfies Cauchy!
Exercise 3.4. Finish up from here.
for all rational numbers x < y < z < t that form an arithmetic progression.
Solution. As before, we see that linear functions f (x) = kx + c satisfy the condition. We
could shift to 0 as before if we like, but for this problem it will turn out to make not a
difference, so Ill cheat and tell you to not bother.
Now, lets clean up the equation a little by writing it as
f (a) + f (a + 3d) = f (a + d) + f (a + 2d).
for d > 0. This has a lot of terms in it, and itd be great if we get a lot of them to cancel
each other off. The trick is to try to make more things cancel by writing down the shifted
version
f (a d) + f (a + 2d) = f (a) + f (a + d)
5
Evan Chen (October 18, 2016) 4 Cauchys Functional Equation Over R
So the main idea of this solution was that by shifting a little, we could cause several
terms to cancel off. That leads us back to Jensens equation.
There exists (a, b) and > 0 such that (x a)2 + (f (x) b)2 > for every x
(i.e. the graph of f omits some disk, however small).
Solution. We claim f (x) = x and f (x) = 0 are the only solutions (which both work).
According to the theorem, to prove f is linear it suffices to show f is nonnegative over
some nontrivial interval. Now,
f (t2 ) = f (t)2 0
for any t, meaning f is bounded below on [0, ) and so we conclude f (x) = cx for some
c. Then cxy = (cx)(cy) implies c {0, 1}, as claimed.
6
Evan Chen (October 18, 2016) 5 More Examples
In general, as far as olympiad contexts, the most common ways to get from additive to
linear are:
The problem gives you that the function f is continuous. It is extremely rare that
you need to prove continuity yourself; in fact I personally cannot think of a single
functional equation in which continuity is a useful intermediate step.
5 More Examples
Here are some more examples of R R equations.
Solution. For this problem, we claim the only answer is the constant function f = 0. As
usual our first move is to take the all-zero setting, which gives f (0) = 0.
Now, lets step back: can we do anything that will make lots of terms go away? Theres
actually a very artificial choice that will do wonders. It is motivated by the battle cry:
So we do the most blithely stupid thing possible. See that x2 + y and x27 + 2y up there?
Lets make them equal in the rudest way possible:
x2 + y = x27 + 2y y = x2 x27 .
This is a common trick: see if you can make a substitution that will kill off two terms.
Solution. First of all, the x y and x + y everywhere are a mess, so we replace them
with a = x + y and b = x y (this doesnt lose any information). Then x2 y 2 = ab,
and also 2x = a + b, 2y = a b. So, the equation is just saying that
7
Evan Chen (October 18, 2016) 6 Three More Tricks
We should keep this in our minds as we proceed.2 One other remark worth making is
that the left-hand side is in fact zero for f (x) cx, which leads to an observation that if
f is a solution, then so is f + 2016x, say. This tells us a bit more about what the solution
space might look like.
Plugging in a = b = 0, then we get 0 = 0, not helpful. Plugging in just one zero term
a = 0 is more fruitful: we derive bf (0) = 0, so f (0) = 0.
Next, assume a, b 6= 0. We do the following nice trick: if we divide by ab, we obtain
f (a) f (b)
= a2 b2 .
a b
Youll notice that the a and b terms are completely isolated now! That is, we can write
f (a) f (b)
a2 = b2 .
a b
Isolated parts. When trying to obtain injective or surjective, watch for isolated
variables or parts of the equation. For example, suppose you have a condition like
(I made that up). Noting that f 0 works, assume f is not zero everywhere. Then
by taking x0 with f (x0 ) 6= 0, one obtains f is injective. (Try putting in y1 and y2 .)
Proving surjectivity can often be done in similar spirit. For example, suppose
By varying y with x fixed we get that f is surjective, and thus we can pick x0 so
that f (x0 ) = 0 and go from there. Surjectivity can be especially nice if every y is
wrapped in an f , say; then each f (y) just becomes replace by an arbitrary real.
2
In general, if linear functions dont work at all or if one gets stuck trying to prove only linear functions
work, it can be worth it to check degree n polynomials in general. Again, for degree reasons there are
usually only finitely many n to check.
8
Evan Chen (October 18, 2016) 7 Heuristics
(again I made that up). This equation is almost symmetric, except for a bump
on the far left where f (x + f (y)) is asymmetric. So if we take the equation with x
and y flipped and then eliminate the common terms, we manage to obtain
f (x + f (y)) = f (y + f (x)).
If weve shown f is injective, we are even done! So often these bumps are what
let you solve a problem. (In particular, dont get rid of the bumps!)
7 Heuristics
At the beginning of a problem:
Figure out what the answer is. For many problems, plug in f (x) = kx + c and find
which k, c work. It may also be worth trying general polynomial functions.
Plug in x = y = 0, x = 0 into the givens, et cetera. See what the most simple
substitutions give first.
Once youve done these obvious steps, some other things to try:
The battle cry DURR WE WANT STUFF TO CANCEL. Plug in things that
make lots of terms cancel (as in Example 5.1) or that make lots of terms vanish
(think x = y = 0).
For equations over N, Z, or Q, induction is often helpful. It can also be helpful over
R as well. The triggers for induction are the same as any other olympiad problem:
you can pin down new values to previous ones.
It may help to rewrite the function in terms of other functions, like we did in
Example 5.2, where looking at g(x) = f (x)/x was useful. Actually, the shift to
zero trick is a special case of this as well.
Often, youll get something like f (x)2 = x2 or f (x) {0, x} or something of this
sort; see the pointwise trap at the end of Example 2.1. When this happens, make
sure you do not automatically assume f (x) = x for each x; this type of equality
holds only for each individual x.
Check the solutions work! Dont get a 6 unnecessarily after solving the problem
just because you forget this trivial step.
This is one useful viewpoint for solving equations. There is a second spiritual perspective
of trying to construct pathological functions that satisfy the problem conditions,
much
like when
we constructed the counterexample to Cauchys functional equation in
Q[ 2] Q[ 2]. This is covered in my more advanced Monsters handout.
9
Evan Chen (October 18, 2016) 8 Practice Problems
8 Practice Problems
Problem 8.1 (Taiwan IMO Training). Find all continuous functions f : R R such
that for any real x and y,
f (f (x + y)) = f (x) + f (y).
Problem 8.5 (Taiwan TST Quiz 2014). Find all (strictly) increasing functions f from
the nonnegative integers to the integers satisfying f (2) = 7 and
Problem 8.8 (ELMO 2014). Find all triples (f, g, h) of injective functions from the set
of real numbers to itself satisfying
Problem 8.9 (ELMO Shortlist 2013 A3). Find all f : R R such that for all x, y R,
Problem 8.10 (IMO 2012/4). Find all functions f : Z Z such that, for all integers
a, b, c that satisfy a + b + c = 0, the following equality holds:
Problem 8.11 (USAMO 2016/4). Find all functions f : R R such that for all real
numbers x and y,
10