Solving Functional Equations for Math Competitions
Solving Functional Equations for Math Competitions
"Mathematics is a collection of cheap tricks and dirty jokes."
Lipman Bers
1914-1993
In this article, we aim to teach you a few cheap tricks which you can employ in math competitions and other areas.
When starting to learn algebra, students are often given a function $f(x)$ and asked to solve a certain relationship, usually $f(x)=0$, for the unknown variable $x$.
This is straight-forward when $f(x)$ is a linear or quadratic equation, but gets more complicated if $f(x)$ is a higher degree polynomial or something different all together.
Here, we are going to look at a new kind of problem. Instead of having a function $f(x)$ be given and solving an equation $f(x)=0$ in terms of the unknown $x$, we will now solve a relationship where the unknowns are themselves functions. These problems frequently appear in math competitions and olympiad-style math. Let's look at a basic example.
If $f(x-1)=x^2+5x+6$, then what is $f(x)$?
Set $y=x-1$ so that $y+1=x$, and substitute these into the above equation.
(Anywhere we see $x-1$, we can instead write $y$, and anywhere we see $x$, we instead write $y+1$.)
This gives
\[ f(y) = (y+1)^2+5(y+1)+6 \]
which simplifies to
\[ f(y) = y^2+7y+12 \]
and hence
\[ f(x) = x^2+7x+12. \]
Simple problems like the above are a great way for you and your math tutor to test your understanding of elementary algebra.
However, in nearly every math competition, more complicated functional equations will be encountered.
Before we look at a more typical example, a few definitions are in order.
If $f:X\to Y$ is a function, then the set $X$ is called the domain of $f$ and the set $Y$ is the codomain of $f$.
We use the symbol $\mathbb{R}$ to stand for the set of real numbers.
Find all functions $f:R\to R$ which satisfy
\[ f(x+y)-f(x-y)=f(x)f(y). \]
We make a few remarks before providing a solution.
The most important piece of data is the given relationship $f(x+y)-f(x-y)=f(x)f(y)$ which is called the functional equation.
A solution to this problem consists of three components:
- describe the form of the general function which satisfies the functional equation (or list all the solutions to the functional equation);
- demonstrate that all functions listed actually satisfy the functional equation;
- prove that any solution of the functional equation is of the form which you describe.
This solution format is especially true in math competitions.
If you don't do the first step, then you cannot do steps 2 or 3; thus you would get 0/7 points.
If you fail to do step 2, you will definitely lose a point, even if your proposed solution is nearly trivial to verify!
The third step is usually the most difficult and requires the most work.
The graders of math competitions are aware of this, so it is possible to receive partial credit for the progress you've made.
As math tutors, we encourage our students to follow the above format and teach them the importance of each step.
In general, we would like to ``substitute'' and then compute as we did in our first example, but this will not always get us to the solution.
A better strategy is to try and manipulate the functional equation (possibly with substitution), compute some explicit values (such as $f(0)$ or something else nice); then use this data to simply guess the answer and check that your guess is indeed correct.
Finally, use a bit of algebra to verify that all solutions look like your guess.
You should be able to see one solution right away, $f(x)=0$. (If you don't, then check that this works.) Can you find any others?
Let's try to manipulate the functional equation and see what comes out.
Notice that the right hand side is \emph{symmetric} in the variables $x$ and $y$, which means that making the exchange $x\mapsto y$ and $y\mapsto x$ leaves the right side unchanged. Now we look at what this does to the left side.
Swapping $x$ and $y$ gives
\[ f(y+x)-f(y-x)=f(y)f(x) \]
so we now know that
\[ -f(x-y) = f(x)f(y)-f(x+y) \]
and
\[ -f(y-x) = f(x)f(y)-f(x+y) \]
hold true, implying $f(x-y)=f(y-x)$.
Making another substitution $x-y=t$, so that $y-x=-t$, we see that $f(t)=f(-t)$ and therefore $f$ is an \emph{even} function.
We are in business, and are nearly done.
Return to the original functional equation and make the substitution $y\mapsto -y$. (We are doing this because we know the right-hand side will remain unchanged, via the relationship we just derived.)
From this we get
\[ f(x-y) - f(x+y) = f(x)f(-y). \]
But we already know $f(-y)=f(y)$ so that
\[ f(x-y) - f(x+y) = f(x)f(y) \]
and now the left-hand side of the above is just $(-1)$ times the left hand side of our original equation.
Thus
\[ -f(x)f(y)=f(x)f(y) \]
and we must have $-f(x)=f(x)$ and conclude that $f(x)=0$ for all $x\in R$.
This argument shows that the \emph{only} solution to the given equation is the function $f(x)=0.$
Here are some things to look for, when doing these yourself or in a math competition:
- must the solution be an even function or an odd function?
- does any particular input make the output easy to compute?
- what relationship does a clever substitution give? (is the function symmetric or antisymmetric in its variables?)
- if we iterate $f$, does that make things simpler?
Once you have found one or more of the above, try and plug it back into the original functional equation and see what happens.
It can seem like magic at first, but with a little practice you will get the hang of it. The most important part is to try \emph{something}.
If you don't see anything, just keep manipulating with algebra and substitution until you do.
In a math competition, time is of the essence; don't allow yourself to simply stare at the given functional equation!
Even in the cases where you aren't able to guess the solution right away, bash the problem with algebra until something comes out.
Let us end this introduction to functional equations by looking at a hard example.
What follows is actually Problem 4 of the 2002 USA Math Olympiad --- the highest level national math contest for US high school students.
Find all functions $f:\mathbb{R}\to \mathbb{R}$ which satisfy $f(x^2-y^2)=xf(x)-yf(y)$.
By looking at the functional equation
\[f(x^2-y^2)=xf(x)-yf(y) \]
can we guess any solutions?
It is clear that $f(x)=x$ satisfies this relationship, but can you think of any others? How about $f(x)=-x$ or $f(x)=2x$? Check that these also work.
We are led to the following guess: the general solution is of the form $f(x)=\alpha x$ for some real number $\alpha$.
If $f(x)=\alpha x$, then we certainly have
\[ f(x^2-y^2) = \alpha(x^2-y^2) = \alpha x^2 - \alpha y^2 = xf(x)-yf(y), \]
so the functional equation is satisfied. (The first two steps of the solution are now done!)
To show that these are the only solutions requires a bit more work.
If $f$ is a function which solves the functional equation, we can find $f(0)$ with relative ease.
See that
\[ f(0) = f(x^2-x^2) = xf(x)-xf(x)=0. \]
Also, if we make the substitution $y\mapsto -y$, what happens?
We have
\[ f(x^2-(-y)^2) = xf(x)+yf(-y) \]
and $(-y)^2=y^2$ implies also that
\[ f(x^2-(-y)^2) = f(x^2-y^2) = xf(x)-yf(y). \]
Putting the above two equations together yields
\[ xf(x)+yf(-y) = xf(x)-yf(y) \]
which can be simplified to $f(-y)=-f(y)$.
This means that $f$ is an \emph{odd} function; now it suffices to find what $f(x)$ is when $x$ is positive - we already know what $f(0)$ must be and if $x$ is negative, then $-x$ is positive so in this case $f(x)=-f(-x)$.
Henceforth, all variables $x,y,$etc. are assumed to be non-negative.
Also if we take $y=0$ in our functional equation, then we get
\[ f(x^2)=xf(x) \]
so the given functional equation is equivalent to
\[ f(x^2-y^2)+f(y^2)=f(x^2). \]
However, we may make the substition $x=\sqrt{u},y=\sqrt{v}$ (because $x,y$ are non-negative) to obtain
\[ f(u-v)+f(v)=f(u). \]
Letting $u=2t$ and $v=t$, we get the futher relationship that $2f(t)=f(2t)$ from our above equation.
Returning to our original functional equation and making the substitution $x=t+1,y=t$ yields
\begin{align*}
f(2t+1) &= (t+1)f(t+1)-tf(t) \\
&= (t+1)f(t-(-1)) - tf(t) \\
&= (t+1)(f(t)+f(1))-tf(t) \\
&= f(t) + (t+1)f(1)
\end{align*}
by using the relationship $f(u-v)+f(v)=f(u)$.
As we already know
\[ f(2t+1) = f(2t)+f(1) = 2f(t)+1 \]
equating these two expressions for $f(2t+1)$ gives us
\[ 2f(t)+f(1) = f(t)+tf(1)+f(1). \]
By subtracting $f(t)+f(1)$ from both sides, we finally arrive at $f(t)=tf(1)$; therefore all solutions must be of the form $f(x)=\alpha x$ for some $\alpha\in \mathbb{R}$.
As a final comment, we want you to be aware of the fact that functional equations come up when solving many classical math problems;
so even if you are not interested in competitive mathematics, it is a worthwhile endeavor to learn the basics of solving functional equations.
At the very least, practicing them will develop your problem solving ability and hopefully show you that persevering through tricky algebra yields a lot of interesting results!
Because of this, we think that these problems are great for math tutors to teach to their students.
