Overview

Functional Equation, often abbreviated as FE, is a famous topic in math olympiads nowadays. This page is for those who have no experience with FEs.

resource: https://web.evanchen.cc/handouts/FuncEq-Intro/FuncEq-Intro.pdf

What is functional equation?

Let us define what a function means.

For sets $X$ and $Y$, A function is an assignment of a value in $Y$ for each $x\in X$; We write it as $f(x)\in Y$

Almost 90% of the FEs in olympiad goes as follows:

Let $X$, $Y$ be sets. Find all functions $f\colon X\rightarrow Y$ such that (some equation)

Here $X$ and $Y$ can be anything, but most of the time it's $\mathbb{Z_{>0}}$, $\mathbb{Z}$, or $\mathbb{R}$.

common mistake

Beginners in FE are often surprised how vast this definition is. Note that $f$ can be anything as long as it's from $A$ to $B$. Yes, anything. We introduce few common pitfalls about the definition of functions:

• $f$ does not need to be a polynomial.
• $f$ does not need to be differentiable.
• $f$ does not need to be continuous.

So think $f$ as an arrow rather than a manipulation. And indeed there's some problem that have a ``strange'' solution which seems like it came out of nowhere. Let us show some examples: some (real olympiad!) problem have solutions with

where $S$ is any subset of $(-\infty, -\frac 23)$.

These are often called as ``monster FE'', and we'll cover this in another module.

Still in other words, $f$ is just an assignment. Some examples are:

• Once you get $f(x)=\pm x$ for all $x\in X$, it is possible that a sign changes depending on the value of $x$. It might be $|x|$, or even the third one in the monster example!
• You get $f(x)=x$ for all $x>1$, but somehow feel stuck from there. It might suddenly be $f(1)=0$ works?

injectivity and surjectivity

Let us introduce new words: In what follows, let $f\colon X\rightarrow Y$ be a function.

• A function $f$ is called injective if $f(a)=f(b)\implies a=b$ for all $a, b\in X$. In other words, $f$ is one-to-one.
• A function $f$ is called surjective if for all $y\in Y$ there exist $x\in X$ such that $f(x)=y$. Thus, $f(x)$ passes through every element of $Y$ as $x$ moves.
• A function is called bijective if it's both injective and surjective.

To understand this more clearly, consider for an integer $m$ that $X=\{1, 2, \dots, m\}$ and $Y=\{1, 2, 3, 4, 5\}$ for example.

1. Show that if $f$ is injective then $m\le 5$ and for $m=4$ give a monster (i.e. random) example of injective $f$.
2. Show that if $f$ is surjective then $m\ge 5$ and similarly give a monster example of surjective $f$.
3. Conclude that if $f$ is bijective then $m=5$, thus we must have $|X|=|Y|$! (However note that this is not true for infinity sets $X$ and $Y$ where $|X|$ and $|Y|$ are not finite.)

More description about injectivity and surjectivity:

• If $f$ is injective, it means we can take away $f$ covered from both sides, e.g. $f(f(x)+1)=f(f(x+1)-1)\implies f(x)+1=f(x+1)-1$.
• If $f$ is surjective, it is useful to assume that $f(u)=0$ (or $1$ or whatever) for some $u$. Sometimes it cancels out a lot of things inserting $u$.

Example

TODO

Practice Problems