Note 1
[A] Functional Equations

Personally I think one of the most difficult sections in olympiad algebra is functional equations. Unlike other sections that involves application of background knowledge, functional equation problems tend to prioritize ingenuity and creativity. This could be a good news if you are cramming for an exam, but I think it is important to solve many problems to find different patterns in problems involving functional equations.

1.1 Foundations

Before we get into what a functional equation is, let’s briefly review the terms related to functions as they appear quite a lot.

Injective Function \begin{align*} &\text {If } f(x_1) = f(x_2), \\ &\text {then } x_1 = x_2 \end{align*}

[Picture]

Surjective Function \begin{align*} &\forall \, y_i \in Y,\ \exists \, x_j \in X \\ &\quad s.t.\ f(x_j) = y_i \end{align*}

[Picture]

Bijective Function \begin{align*} &\forall \, y_i \in Y,\ \exists !\, x_j \in X \\ &\quad s.t.\ f(x_j) = y_i \end{align*}

[Picture]

While we will be using the terms above, it is worth noting other famous terms describing the same functions.

Some people use the term one-to-one for injective, onto for surjective, and one-to-one onto for bijective functions.

As mentioned, we don’t really need other strong backgrounds for functional equations, though there are plenty of techniques to study. However, the terms injective, surjective, and bijective really cannot be stressed enough.

A function \(f\) has an inverse if and only if it is bijective.

This seemingly obvious statement can come very handy. To show it, you can consider the diagrams above. If the function is only injective, then we have inputs with no corresponding output. If \(f\) is surjective only, then there are inputs with two outputs, which is not a function anymore. Another very interesting property to note is strictly increasing and decreasing functions.

A strictly increasing or decreasing function is always injective.

First, note that a strictly increasing function \(f\) have the property where if \(x < y\) then \(f(x) < f(y)\). This satisfies the definition of injective function because \(f\) is strictly increasing. The case for strictly decreasing is proven in analogous way. With these in mind, let’s get started with functional equations!

A functional equation as the name suggest is simply an equation where the variable is a function. To see what it means, let’s solve practice problems. Really, there is nothing more to it and we now just need to keep practicing pattern recognition and thinking creatively. However before starting, there is an important note to keep in mind.

The phrase if and only if cannot be stressed enough! If you think you’ve found all the solutions, chances are you probably haven’t. Many points are taken off because of the lack of the proof for the if and only if condition, and it is always nice to suspect your assumption that you have found all the solutions.

For our first problem, let’s solve a classic problem that involves injection, surjection, and bijection.

Exercise 1.1.1: Classic Problem (\(\bullet \circ \circ \))

Find all functions \(f\) such that \(f(f(x) + f(y)) = x + y\) for all \(x, y \in \mathbb {Z}\) [MATH01-5].

Solution.

Unlike the traditional approach of substituting different values to \(x\) and \(y\), let’s start by substituting \(y = 1\). Substituting, \(f(f(x) + f(1)) = x + 1 = f(f(x + 1) + f(0))\). To find injectivity, surjectivity, or bijectivity of the function \(f\), assume \(f(a) = f(b)\). Then, \(f(f(a) + f(y)) = f(f(b) + f(y))\) and by definition, \(f(a) = f(b)\) leads to \(a = b\). In other words, \(f\) is injective.

Returning to our previous equation \(f(f(x) + f(1)) = f(f(x + 1) + f(0))\), we could see that \(f(x) + f(1) = f(x + 1) + f(0)\) since \(f\) is injective. Rearranging, \(f(x + 1) - f(x) = f(1) - f(0)\) and \(f(x)\) is arithmetic sequence. Therefore let \(f(x) = ax + b\). Substituting to our given equation, \(f(ax + b + ay + b) = a (ax + b + ay + b) + b = x + y\). Solving the equation, \begin{align*} a (ax + b + ay + b) + b &= x + y \\ \left ( a^2 - 1 \right ) x + \left ( a^2 - 1 \right ) y + 2ab + b &= 0 \end{align*}

holds for all \(x, y \in \mathbb {R}\). Thus \(a = \pm 1\) and \(b = 0\). Therefore, \(f(x) = \pm x\) are all solutions.

Continuing from this problem, we have a harder problem that requires smart substitutions.

Exercise 1.1.2: 2008 IMO Problem 4 (\(\bullet \bullet \bullet \))

Find all functions \(f: (0, \infty ) \mapsto (0, \infty )\) that satisfy the following equation for all positive reals \(a, b, c, d\) where \(ab = cd\). \[ \frac { f(a)^2 + f(b)^2 }{f(c^2) + f(d^2)} = \frac {a^2 + b^2}{c^2 + d^2} \]

Solution.

First, let’s start with what we can observe from the problem. The first thing that we can see is that we have squares everywhere. The second thing to note is that substituting \(a = b = c = d = 1\) gives us \(f(x) = 1\). We can also notice that if we substitute \((n, n, n, n)\) we get \(f(n)^2 = f(n^2)\).

With the observations in mind, what we can try is getting rid of the square by substituting \((\sqrt {x}, \sqrt {x}, 1, x)\). This will lead us to following equations. \begin{align*} \frac { f(\sqrt {x})^2 + f(\sqrt {x})^2 }{ 1 + f(x^2) } &= \frac {x + x}{1 + x^2} \\ \frac { 2f(x) }{ 1 + f(x)^2 } &= \frac {2x}{1 + x^2} \\ 2f(x) (1 + x^2) &= 2x(1 + f(x)^2) \end{align*}

Continuing, we can rearrange the equations to solve for \(f\). \begin{align*} xf(x)^2 - (1 + x^2)f(x) + x &= 0 \\ (xf(x) - 1) (f(x) - x) &= 0 \\ \therefore f(x) = x \text { or } f(x) &= \frac {1}{x} \end{align*}

Now we can see that if a function \(f\) satisfy the equation given by the problem, then \(f(x) = x\) or \(f(x) = \frac {1}{x}\). Moreover, if \(f(x) = x)\) or \(f(x) = \frac {1}{x}\), then \(f\) satisfies the original equation as we can see from direct substitution.

If we end our solution here thinking that we have solved the problem, we will lose points for not showing that \(x\) and \(\frac {1}{x}\) are the only solutions. Although we showed the if and only if condition, we have not showed that \(f\) is not a piece-wise function.

Lemma. \(f(x) = x\) and \(f(x) = \frac {1}{x}\) are the only solutions to the equation.

Proof. For the sake of contradiction, let \(f(\alpha ) \neq \alpha \) and \(f(\beta ) \neq \frac {1}{\beta }\) for \(\alpha , \beta \neq 1\). By our previous conclusions, we can see that it implies \(f(\alpha ) = \frac {1}{\alpha }\) and \(f(\beta ) = \beta \).

Substitute \((\sqrt {\alpha }, \sqrt {\beta }, 1, \sqrt {\alpha \beta })\) to eliminate the squares and use both \(\alpha \) and \(\beta \). \begin{align*} \frac { f(\sqrt {\alpha })^2 + f(\sqrt {\beta })^2 } { f(1) + f(\alpha \beta ) } &= \frac {\alpha + \beta }{1 + \alpha \beta } \\ \frac { \frac {1}{\alpha } + \beta }{ 1 + f(\alpha \beta ) } &= \frac {\alpha + \beta }{1 + \alpha \beta } \end{align*}

Notice that \(f(\alpha \beta )\) is either \(\alpha \beta \) or \(\frac {1}{\alpha \beta }\). Therefore, let \(f(\alpha \beta ) = \alpha \beta \). Solving the equation, the following equations are obtained. \begin{align*} \frac { \frac {1}{\alpha } + \beta }{ 1 + f(\alpha \beta ) } &= \frac {\alpha + \beta }{1 + \alpha \beta } \\ \frac { \frac {1}{\alpha } + \beta }{ 1 + \alpha \beta } &= \frac {\alpha + \beta }{1 + \alpha \beta } \\ \frac {1}{\alpha } &= \alpha \end{align*}

This contradicts with the fact that \(\alpha \neq 1\). Continuing, let \(f(\alpha \beta ) = \frac {1}{\alpha \beta }\). \begin{align*} \frac { \frac {1}{\alpha } + \beta }{ 1 + f(\alpha \beta ) } \displaybreak &= \frac {\alpha + \beta }{1 + \alpha \beta } \\ \frac { \frac {1}{\alpha } + \beta }{ 1 + \frac {1}{\alpha \beta } } &= \frac {\alpha + \beta }{1 + \alpha \beta } \\ \frac {\beta + \alpha \beta ^2}{\alpha \beta + 1} &= \frac {\alpha + \beta }{1 + \alpha \beta } \\ \alpha \beta ^2 &= \alpha \\ \beta ^2 &= 1 \end{align*}

This also contradicts with \(\beta \neq 1\). Therefore, there exists no \(\alpha , \beta \neq 1\) such that \(f(\alpha ) \neq \alpha \) and \(f(\beta ) \neq \frac {1}{\beta }\). □

Hence, \(f(x) = x\) and \(f(x) = \frac {1}{x}\) are the only solutions.

As you probably have noticed from the solution, while vast amount of knowledge in different functions may come handy, ingenuity and clever substitution would do most of the work when solving problems. Here is another problem on using clever substitutions.

Exercise 1.1.3: 2020 Baltic Way Problem 4 (\(\bullet \circ \circ \))

Find all functions \(f: \mathbb {R} \rightarrow \mathbb {R}\) that satisfy the following for all \(x, y \in \mathbb {R}\). \[ f(f(x) + x + y) = f(x + y) + yf(y) \]

(Video Solution)

Solution.

First, let’s start by doing typical substitutions. Substituting \(x = y = 0\) gives \(f(f(0)) = f(0)\) and \(x = -y\) gives \(f(f(x)) = f(0) - xf(-x)\). Also, trying \(y = 0\) gives \(f(f(x) + x) = f(x)\). Looking at the last observation, we could assume that \(f(x) = 0\). Moreover our first observation also suggests that \(f(0) = 0\). With the observations, let’s first investigate the value of \(f(0)\).

Consider the following equation by the last observation with \(y = f(x) + x\). \begin{align*} f(x) &= f(y) = f(f(y) + y) = f(f(x) + f(x) + x) \\ &= f(x + f(x)) + f(x) f(f(x)) = f(x) + f(x) f(f(x)) \end{align*}

Therefore, \(f(x) f(f(x)) = 0\) and \(f(0) f(f(0)) = 0\). Note that because \(f(f(0)) = f(0)\), \(f(0)^2 = 0\) and \(f(0) = 0\) holds. Indeed \(f(0) = 0\)!

Continuing, substitute \(x = 0\) to the given equation. \[ f(f(0) + 0 + y) = f(y) = f(0 + y) + y f(y) \] In other words, \(y f(y) = 0\) holds for all \(y \in \mathbb {R}\). Specially, \(f(y) = 0\) for all \(y \neq 0\) and we have found that \(f(0) = 0\). Therefore, \(f(x) = 0\) for all \(x \in \mathbb {R}\) is the only solution.

In this problem, using the observation carefully and letting \(y = f(x) + x\) was the key part of the solution. There are many topics to discuss even if it requires less prerequisite knowledge to actually solve the problem. With the intuition discussed in this note, let’s discuss few important topics and patterns that are widely used.