Functional Equations: Problems with SolutionsThe following problems are related to functional equations. Many of the problems were given at national and international mathematical competitions and olympiads, and thus are challenging. You may want to read first an introductory text to Functional equations.
Problem 1
This is a classical
example of a problem that can be solved using
mathematical induction.
Notice that if we set \( x=1 \) and \( y=n \)
in the original equation we get \( f(n+1)=f(n)+1 \),
and since \( f(1)=2 \) we have \( f(n)=n+1 \) for
every natural number
\( n \). Similarly for \( x=0 \) and \( y=n \) we get \( f(0)n=f(n)-1=n \), i.e.
\( f(0) \). Now our goal is to find \( f(z) \) for each
\( z\in\mathbb{Z} \). Substituting \( x=-1 \) and \( y=1 \)
in the original equation gives us \( f(-1)=0 \),
and setting \( x=-1 \) and \( y=n \) gives
\( f(-n)=-f(n-1)+1=-n+1 \). Hence \( f(z)=z+1 \) for each
\( z\in\mathbb{Z} \). Now we have to determine \( f\Big( \frac 1n\Big) \).
Plugging \( x=n \) and \( y= \frac 1n \) we get
\[ f(1)=(n+1)f\Big( \frac 1n\Big)-
f\Big(n+ \frac 1n\Big)+1. \quad\quad\quad\quad\quad(1) \] Furthermore
for \( x=1 \) and \( y=m+ \frac 1n \) we get \( f\Big(m+1+ \frac
1n\Big)=f\Big(m+ \frac 1n\Big)+1 \), hence by
the mathematical induction
\( f\Big(m+ \frac 1n\Big)=m+f\Big( \frac 1n\Big) \). From
(1) we now have \[ f\Big(\frac 1n\Big)=\frac 1n+1,\]
for every natural number \( n \). Furthermore for \( x=m \) and
\( y= \frac 1n \) we get
\( f\Big( \frac mn\Big)= \frac mn+1 \), i.e. \( f(r)=r+1 \),
for every positive rational number \( r \).
Setting \( x=-1 \) and
\( y=r \) we get \( f(-r)=-f(r-1)+1=-r+1 \) as well hence
\( f(x)=x+1 \), for each
\( x\in\mathbb{Q} \).
Verification: Since \( xy+1=(x+1)(y+1)-(x+y+1)+1 \), for all \( x,y\in\mathbb{Q} \), \( f \) is the solution to our equation.
Problem 2 (Belarus 1997)
Notice that \( g(x)=0 \) and \( g(x)=2 \)
are obviously solutions to the given equation.
Using mathematical induction it is not difficult to
prove
that if \( g \) is not equal to one of these two functions then
\( g(x)=x \) for all \( x\in\mathbb{Q} \).
It is also easy to prove that \( g(r+x)=r+g(x) \) and
\( g(rx)=rg(x) \), where \( r \) is rational and \( x \) real
number. Particularly from the second equation for
\( r=-1 \) we get \( g(-x)=-g(x) \), hence setting
\( y=-x \) in the initial equation gives \( g(x)^2=g(x^2) \).
This means that
\( g(x)\geq 0 \) for \( x\geq 0 \).
Now we use the standard method of extending to
\( \mathbb{R} \). Assume that \( g(x)< x \).
Choose \( r\in\mathbb{Q} \) such that \( g(x)< r< x \).
Then \[ r> g(x)=g(x-r)+r\geq
r,\] which is clearly a contradiction.
Similarly from
\( g(x)> x \)
we get another contradiction.
Thus we must have \( g(x)=x \) for every \( x\in
\mathbb{R} \).
\noindent It is easy to verify that all
three functions satisfy the
given functional equation.
Problem 3
The domain of this function is
\( \mathbb{R} \), so there isn\( \prime \)t much hope that this can be solved
using mathematical induction.
Notice that \( f(f(x))-f(x)=x \) and if \( f(x)=f(y) \) then clearly
\( x=y \). This means that the function is injective. Since
\( f(f(0))=f(0)+0=f(0) \), because of injectivity we must have
\( f(0)=0 \), implying
\( f(f(0))=0 \). If there were another \( x \) such that \( f(f(x))=0=f(f(0)) \),
injectivity would imply \( f(x)=f(0) \) and
\( x=0 \).
Problem 4
Setting
\( m=1 \) and \( n \) first, and \( m=n \), \( n=1 \) afterwards we get
\[ f(f(1)+f(n))=f(f(1))+f(n),\quad f(f(n)+f(1))=f(f(n))+f(1).\]
Let us emphasize that this is one standard idea if the
expression on one side is symmetric with respect to the
variables while the expression on the other side is not.
Now we have
\( f(f(n))=f(n)-f(1)+f(f(1))=f(n)-2+f(2)=f(n)+2 \).
From here we conclude that \( f(n)=m \) implies \( f(m)=m+2 \)
and now the induction gives \( f(m+2k)=m+2k+2 \), for every
\( k\geq 0 \).
Specially if \( f(1)=2 \) then \( f(2n)=2n+2 \)
for all positive integers \( n \).
The injectivity of \( f \) gives that at odd numbers
(except 1) the function has to take odd values.
Let \( p \) be the smallest natural number
such that for some \( k \)
\( f(k)=2p+1 \). We have
\( f(2p+2s+1)=2p+2s+3 \) for \( s\geq 0 \).
Therefore the numbers \( 3,5,\ldots,2p-1 \) are mapped into
\( 1,3,\ldots,2p+1 \). If \( f(t)=1 \) for some \( t \),
then for \( m=n=t \)
\( 4=f(2)=f(f(t)+f(t))=f(f(t))+f(t)=3 \), which is a
contradiction.
If for some \( t \) such that \( f(t)=3 \) then
\( f(3+2k)=5+2k \), which is a contradiction to the existence
of such \( t \). It follows that the numbers
\( 3,5,\ldots,2p-1 \) are mapped into \( 5,7,\ldots,2p+1 \).
Hence \( f(3+2k)=5+2k \). Thus the solution is \( f(1)=2 \) and
\( f(n)=n+2 \), for \( n\geq 2 \).\\
It is easy to verify that the function satisfies the
given conditions.
Problem 5 (BMO 1997, 2000)
In probelms of this type it is
usually easy to prove that the functions are
injective or surjective, if the functions are injective/surjective.
In this case for \( x=0 \) we get
\( f(f(y))=y+f(0)^2 \).
Since the function on the right-hand side
is surjective
the same must hold for the function on the left-hand side.
This implies the surjectivity of \( f \).
Injectivity is also easy to establish. Now there exists
\( t \) such that \( f(t)=0 \) and substitution \( x=0 \)
and \( y=t \) yields \( f(0)=t+f(0)^2 \).
For \( x=t \) we get
\( f(f(y))=y \). Therefore
\( t=f(f(t))=f(0)=t+f(0)^2 \), i.e. \( f(0)=0 \).
Replacing \( x \) with \( f(x) \) gives
\[ f(f(x)x+f(y))=x^2+y,\]
hence \( f(x)^2=x^2 \) for every real number \( x \).
Consider now the two cases:
\noindent\emph{First case \( f(1)=1 \)}. Plugging \( x=1 \)
gives \( f(1+f(y))=1+y \), and after taking squares
\( (1+y)^2=f(1+f(y))^2=(1+f(y))^2=1+2f(y)+f(y)^2=1+2f(y)+y^2 \).
Clearly in this case we have \( f(y)=y \) for every real
\( y \).
\noindent\emph{Second case \( f(1)=-1 \)}. Plugging \( x=-1 \)
gives \( f(-1+f(y))=1+y \), and after taking squares
\( (1+y)^2=f(-1+f(y))^2=(-1+f(y))^2=1-2f(y)+f(y)^2=1-2f(y)+y^2 \).
Now we conclude \( f(y)=-y \) for every real number
\( y \).
\noindent It is easy to verify that
\( f(x)=x \) and \( f(x)=-x \) are indeed the solutions.
Problem 6 (IMO 1979, shortlist)
This is a clasical example
of the equation that solution is based on a careful
choice of values that are plugged in a functional equation.
Plugging in \( x=y=0 \) we get \( f(0)=0 \). Plugging in \( y=-1 \) we get
\( f(x)=-f(-x) \). Plugging in \( y=1 \) we get \( f(2x+1)=2f(x)+f(1) \) and
hence \( f(2(u+v+uv)+1)=2f(u+v+uv)+f(1)=2f(uv)+2f(u)+2f(v)+f(1) \) for
all real \( u \) and \( v \). On the other hand, plugging in \( x=u \) and
\( y=2v+1 \) we get \( f(2(u+v+uv)+1)=f(u+(2v+1)+u(2v+1))=f(u)+2f(v)+
f(1)+f(2uv+u) \). Hence it follows that \( 2f(uv)+2f(u)+2f(v)+f(1)=
f(u)+2f(v)+f(1)+f(2uv+u) \), i.e., \[ f(2uv+u)=2f(uv)+f(u).\quad\quad\quad\quad\quad (1)\]
Plugging in \( v=-1/2 \) we get \( 0=2f(-u/2)+f(u)=-2f(u/2)+f(u) \).
Hence, \( f(u)=2f(u/2) \) and consequently \( f(2x)=2f(x) \) for all
reals. Now (1) reduces to \( f(2uv+u)=f(2uv)+ f(u) \). Plugging in
\( u=y \) and \( x=2uv \), we obtain \( f(x)+f(y)=f(x+y) \) for all nonzero
reals \( x \) and \( y \). Since \( f(0)=0 \), it trivially holds that
\( f(x+y)=f(x)+f(y) \) when one of \( x \) and \( y \) is \( 0 \).
Problem 7
After some attempts we can see that
none of the first three methods leads to a progress.
Notice that the function \( g \) of the right-hand side
has exactly \( 2 \) fixed points and that the function \( g\circ g \)
has exactly 4 fixed points. Now we will prove that there
is no function \( f \) such that \( f\circ f=g \).
Assume the contrary. Let \( a,b \) be the fixed points of
\( g \), and \( a,b,c,d \) the fixed points of \( g\circ g \).
Assume that \( g(c)=y \). Then
\( c=g(g(c))=g(y) \), hence \( g(g(y))=g(c)=y \) and \( y \) has to be
on of the fixed points of \( g\circ g \). If \( y=a \) then from
\( a=g(a)=g(y)=c \) we get a contradiction. Similarly
\( y\neq b \), and since \( y\neq c \) we get \( y=d \).
Thus \( g(c)=d \) and \( g(d)=c \).
Furthermore we have \( g(f(x))=f(f(f(x)))=f(g(x)) \).
Let \( x_0\in \{a,b\} \).
We immediately have \( f(x_0)=f(g(x_0))=g(f(x_0)) \), hence
\( f(x_0)\in\{a,b\} \). Similarly if \( x_1\in\{a,b,c,d\} \)
we get \( f(x_1)\in\{a,b,c,d\} \), and now we will prove that
this is not possible.
Take first \( f(c)=a \). Then \( f(a)=f(f(c))=g(c)=d \) which is
clearly impossible. Similarly \( f(c)\neq b \) and
\( f(c)\neq c \) (for otherwise \( g(c)=c \)) hence \( f(c)=d \).
However we then have
\( f(d)=f(f(c))=g(c)=d \), which is a contradiction, again.
This proves that the required \( f \) doesn\( \prime \)t exist.
Problem 8
Obviously \( f(x)\equiv 1 \) is one solution to the problem.
The idea is to find \( y \) such that
\( yf(x)=x+y \) and use this to determine
\( f(x) \). For every \( x \) such that
\( \frac{x}{f(x)-1}\geq 0 \)
we can find such \( y \) and from the given condition we get
\( f(x)=1 \). However this is a contradiction since we got that
\( f(x)> 1 \) implies
\( f(x)=1 \). One of the consequences is that \( f(x)\leq 1 \).
Assume that
\( f(x)< 1 \) for some \( x \). From the given equation we
conclude that
\( f \) is non-increasing (because \( f(yf(x))\leq 1 \)).
Let us prove that \( f \) is decreasing. In order to do that
it is enough to prove that \( f(x)< 1 \), for each \( x \).
Assume that \( f(x)=1 \) for every
\( x\in(0,a) \) (\( a> 0 \)). Substituting
\( x=y= \frac {2a}{3} \) in the given equation we get the
obvious contradiction. This means that the function is
decreasing and hence it is injective.
Again everything will revolve around the idea of getting rid of
\( f(yf(x)) \).
Notice that
\( x+y> yf(x) \), therefore
\[ f(x)f(yf(x))=f(x+y)=f(yf(x)+x+y-yf(x))=f(yf(x))f\Big(f\Big(yf(x)\Big)(x+y-yf(x))\Big),\]
i.e. \( f(x)=f\Big(f\Big(yf(x)\Big)(x+y-yf(x))\Big) \). The injectivity
of \( f \) implies that
\( x=f\Big(yf(x)\Big)(x+y-yf(x)) \).
If we plug \( f(x)=a \)
we get \[ f(y)=\frac{1}{1+\alpha z},\] where
\( \alpha= \frac{1-f(a)}{af(a)} \), and according to
our assumption
\( \alpha> 0 \).\\
It is easy to verify that \( f(x)= \frac{1}{1+\alpha x} \), for
\( \alpha\in\mathbb{R}^+ \), and \( f(x)\equiv 1 \) satisfy the
equation.
Problem 9
Let us first solve the problem under the assumption that
\( g(\alpha)=0 \) for some \( \alpha \).
Setting \( y=\alpha \) in the given equation yields \( g(x)=(\alpha+1)
f(x)-xf(\alpha) \). Then the given equation becomes \( f(x+g(y))=
(\alpha+1-y)f(x)+(f(y)-f(\alpha))x \), so setting \( y=\alpha+1 \) we
get \( f(x+n)=mx \), where \( n=g(\alpha+1) \) and \( m=f(\alpha+1)-
f(\alpha) \). Hence \( f \) is a linear function, and consequently \( g \)
is also linear. If we now substitute \( f(x)=ax+b \) and \( g(x)=cx+d \)
in the given equation and compare the coefficients, we easily find
that \[ f(x)=\frac{cx-c^2}{1+c}\hspace{3mm}\mbox{and}\hspace{3mm}
g(x)=cx-c^2,\hspace{5mm}c\in\mathbb{R}\setminus\{-1\}.\] Now we
prove the existence of \( \alpha \) such that \( g(\alpha)=0 \). If
\( f(0)=0 \) then putting \( y=0 \) in the given equation we obtain
\( f(x+g(0))=g(x) \), so we can take \( \alpha=-g(0) \).
Now assume that \( f(0)=b\neq 0 \). By replacing \( x \) by \( g(x) \) in the
given equation we obtain \( f(g(x)+g(y))=g(x)f(y)
-yf(g(x))+g(g(x)) \) and, analogously,
\( f(g(x)+g(y))=g(y)f(x)-xf(g(y))+g(g(y)) \). The given functional
equation for \( x=0 \) gives \( f(g(y))=a-by \), where \( a=g(0) \). In
particular, \( g \) is injective and \( f \) is surjective, so there
exists \( c\in\mathbb{R} \) such that \( f(c)=0 \). Now the above two
relations yield \[ g(x)f(y)-ay+g(g(x))=g(y)f(x)-ax+g(g(y)).
\quad\quad\quad\quad\quad (1)\] Plugging \( y=c \) in \( (1) \) we get \( g(g(x))=g(c)f(x)-ax+
g(g(c))+ac=kf(x)-ax+d \). Now \( (1) \) becomes \( g(x)f(y)+kf(x)=
g(y)f(x)+kf(y) \). For \( y=0 \) we have \( g(x)b+kf(x)=af(x)+kb \), whence
\[ g(x)=\frac{a-k}bf(x)+k.\] Note that \( g(0)=a\neq k=g(c) \), since \( g \) is
injective. From the surjectivity of \( f \) it follows that \( g \) is
surjective as well, so it takes the value \( 0 \).
Problem 10 (IMO 1992, shortlist)
This is a typical example
of a problem that is solved using recurrent equations.
Let us define \( x_n \) inductively as \( x_n=f(x_{n-1}) \), where
\( x_0\geq0 \) is a fixed real number. It follows from the given
equation in \( f \) that \( x_{n+2}=-ax_{n+1}+ b(a+b)x_n \). The general
solution to this equation is of the form \[ x_n=\lambda_1b^n
+\lambda_2(-a-b)^n,\] where \( \lambda_1,\lambda_2\in\mathbb{R} \)
satisfy \( x_0=\lambda_1+\lambda_2 \) and \( x_1=\lambda_1b-
\lambda_2(a+b) \). In order to have \( x_n\geq 0 \) for all \( n \) we must
have \( \lambda_2=0 \). Hence \( x_0=\lambda_1 \) and \( f(x_0)=x_1=
\lambda_1b=bx_0 \). Since \( x_0 \) was arbitrary, we conclude that
\( f(x)=bx \) is the only possible solution of the functional
equation. It is easily verified that this is indeed a solution.
Problem 11 (Vietnam 2003)
We clearly have that
\( \frac x2\in F \), hence \( \alpha\leq \frac 12 \).
Furthermore for every function \( f\in F \)
we have \( f(x)\geq \frac x3 \).
The idea is the following: Denote
\( \frac 13=\alpha_1 \) and form a sequence
\( \{\alpha_n\} \) for which \( f(x)\geq \alpha_n x \) and which
will (hopefully) tend to \( \frac 12 \).
This would imply that
\( \alpha\geq \frac 12 \), and hence \( \alpha= \frac 12 \).
Let us constract a recurrent relation for \( \alpha_k \).
Assume that \( f(x)\geq
\alpha_k x \), for every \( x\in\mathbb{R}^+ \).
From the given inequality we have
\[ f(3x)\geq f(f(2x))+x\geq \alpha_k f(2x)+x\geq
\alpha_k\cdot\alpha_k\cdot 2x+x=\alpha_{k+1}\cdot 3x.\]
This means that
\( \alpha_{n+1}= \frac{2\alpha_n^2+1}{3} \). Let us prove that
\( \lim_{n\rightarrow+\infty}\alpha_n= \frac 12 \).
This is a standard problem. It is easy to prove that
the sequence \( \alpha_k \) is increasing and bounded above by
\( \frac 12 \). Hence it converges and its limit
\( \alpha \) satisfies
\( \alpha= \frac{2\alpha^2+1}{3} \), i.e. \( \alpha= \frac 12 \)
(since \( \alpha< 1 \)).
Problem 12
Our first goal is to express
\( f \) and \( g \) using \( h \) and get the equation involving \( h \) only.
First taking \( y=x \) and substituting \( g(0)=a \) we get
\( f(2x)=4h(x)-a. \) Furthermore by putting
\( y=0 \) we get \( g(x)=2h(x)+2b-4h\Big( \frac x2\Big)+a \), where
\( h(0)=b \). Now the original equation can be written as
\[ 2\left[h\Big( \frac
{x+y}{2}\Big)+h\Big( \frac{x-y}{2}\Big)\right]+h(x-y)+
b=h(x)+h(y). \quad\quad\quad\quad\quad (1)
\]
Let \( H(x)=h(x)-b \). These "longer" linear expressions
can be easily handled
if we express functions in form of the sum of an
even and odd function, i.e.
\( H(x)=H_e(x)+H_o(x) \).
Substituting this into (1)
and writing the same expressions for \( (-x,y) \) and \( (x,-y) \)
we can add them together and get: \[ 2\left[H_e\Big( \frac
{x-y}{2}\Big)+H_e\Big( \frac{x+y}{2}\Big)\right]+
H_e(x-y)=H_e(x)+H_e(y). \quad\quad\quad\quad\quad (2)\]
If we set \( -y \) in this expression
and add to (2)
we get (using \( H_e(y)=H_e(-y) \))
\[ H_e(x+y)-H_e(x-y)=2H_e(x)+2H_e(y).\]
The last equation is not very difficult.
Mathematical induction yields
\( H_e(r)=\alpha r^2 \), for every
rational number \( r \). From the continuity we get
\( H_e(x)=\alpha x^2 \). Similar method gives the simple relation
for \( H_o \)
\[ H_o(x+y)+H_o(x-y)=2H_o(x).\]
This is a Cauchy equation
hence
\( H_o(x)=\beta x \). Thus \( h(x)=\alpha x^2+\beta x+b \) and
substituting for \( f \) and \( g \) we get:
\[ f(x)=\alpha x^2+2\beta
x+4b-a,\quad g(x)=\alpha x^2+a.\] It is easy to verify
that these functions satisfy the given conditions.
Problem 13
It is not hard to see that for
\( x=y=0 \)
we get \( (f(0)-1)^2=0 \), i.e. \( f(0)=1 \).
Furthermore, setting \( x=1 \) and
\( y=-1 \) gives \( f(-1)=f(1)f(-1) \), hence \( f(-1)=0 \) or \( f(1)=1 \).
We will separate this into two cases:
Now let us solve the problem where \( f:\mathbb{R}\rightarrow\mathbb{R} \). Notice that we haven\( \prime \)t used that the range is \( \mathbb{Q} \), hence we conclude that for all rational numbers \( q \) \( f(q)=q+1 \), or \( f(q)\equiv 1 \). If \( f(q)=1 \) for all rational numbers \( q \), it can be easily shown that \( f(x)\equiv 1 \). Assume that \( f(q)\not\equiv 1 \). From the above we have that \( g(x)+g(y)=g(x+y) \), hence it is enough to prove monotonicity. Substitute \( x=y \) in (3) and use \( g(2x)=2g(x) \) to get \( g(x^2)=-g(x)^2 \). Therefore for every positive \( r \) the value \( g(r) \) is non-positive. Hence if \( y> x \), i.e. \( y=x+r^2 \) we have \( g(y)=g(x)+g(r^2)\leq g(x) \), and the function is decreasing. This means that \( f(x)=1+\alpha x \) and after some calculation we get \( f(x)=1+x \). It is easy to verify that so obtained functions satisfy the given functional equation.
Problem 14
First notice that the
solution of this functional equation is not one of the
common solutions that we are used to work with. Namely
one of the solutions is
\( f(x)=x+ \frac 1x \) which tells us that this equality is unlikely
to be shown reducing to the Cauchy equation.
First, setting \( x=y=z=1 \) we get \( f(1)=2 \) (since \( f(1)> 0 \)).
One of the properties of the solution suggested above is
\( f(x)=f(1/x) \),
and proving this equality will be our next step.
Putting \( x=ts \), \( y=\frac ts \), \( z=\frac st \) in (i) gives
\[
f(t)f(s)=f(ts)+f(t/s).\quad\quad\quad\quad\quad (1)\]
In particular,
for \( s=1 \) the last equality yields \( f(t)=f(1/t) \); hence \( f(t)\geq
f(1)=2 \) for each \( t \). It follows that there exists \( g(t)\geq1 \)
such that \( f(t)=g(t)+ \frac1{g(t)} \).
Now it follows by
induction from (1)
that \( g(t^n)=g(t)^n \) for every integer \( n \),
and therefore \( g(t^q)= g(t)^q \) for every rational \( q \).
Consequently, if \( t> 1 \) is fixed, we have \( f(t^q)=a^q+a^{-q} \),
where \( a=g(t) \). But since the set of \( a^q \) (\( q\in\mathbb{Q} \)) is
dense in \( \mathbb{R}^+ \) and \( f \) is monotone on \( (0,1] \) and
\( [1,\infty) \), it follows that \( f(t^r)= a^r+a^{-r} \) for every real
\( r \). Therefore, if \( k \) is such that \( t^k=a \), we have
\[ f(x)=x^k+x^{-k}
\hspace{5mm}\mbox{for every }x \in\mathbb{R}. \]
Problem 15
It is not hard to see that \( f(x)=x+1 \) is a solution.
Let us prove that this is the only solution. Using the
given conditions we get \[ f(x)^2=xf(x+1)+1\leq
x(2(x+1))+1< 2(1+x)^2,\] i.e.
\( f(x)\leq \sqrt{2}(1+x) \). With this we have found
the upper bound for \( f(x) \).
Since our goal is to prove \( f(x)=x+1 \)
we will use the same method for lowering the upper bound. Similarly
we get
\[ f(x)^2=xf(x+1)+1\leq x(\sqrt{2}(x+1))+1< 2^{1/4}(1+x)^2.\]
Now it is clear that we should use induction to prove
\[ f(x)< 2^{1/2^k}(1+x),\] for every \( k \).
However this is shown in the same way as the previous
two inequalities.
Since \( 2^{1/2^k}\rightarrow 1 \) as
\( k\rightarrow+\infty \), hence for fixed \( x \) we can\( \prime \)t
have
\( f(x)> x+1 \). This implies \( f(x)\leq x+1 \)
for every real number \( x\geq
1 \).
It remains to show that
\( f(x)\geq x+1 \), for \( x\geq 1 \).
We will use the similar argument.
From the fact that the range is \( [1,+\infty) \) we get
\( \frac{f(x)^2-1}{x}=f(x+1)\geq 1 \), i.e.
\( f(x)\geq
\sqrt{x+1}> x^{1/2} \). We further have
\( f(x)^2=1+xf(x+1)> 1+x\sqrt{x+2}> x^{3/2} \)
and similarly by induction
\[ f(x)> x^{1-1/2^k}.\]
Passing to the limit we further have \( f(x)\geq
x \). Now again from the given equality
we get \( f(x)^2=1+xf(x+1)\geq
(x+1/2)^2 \), i.el \( f(x)\geq x+1/2 \).
Using the induction we get \( f(x)\geq
x+1- \frac{1}{2^k} \), and passing to the limit
we get the required inequality \( f(x)\geq x+1 \).
Problem 16 (IMO 1999, probelm 6)
Let \( A=\{f(x)\,|\,
x\in\mathbb{R}\} \), i.e. \( A=f(\mathbb{R}) \).
We will determine the value of the function on \( A \).
Let \( x=f(y)\in A \), for some \( y \).
From the given equality we have \( f(0)=f(x)+x^2+f(x)-1 \), i.e.
\[ f(x)= \frac{c+1}{2}-\frac{x^2}{2},\] where \( f(0)=c \).
Now it is clear that we have to analyze set \( A \) further.
Setting
\( x=y=0 \) in the original equation
we get \( f(-c)=f(c)+c-1 \), hence \( c\neq 0 \).
Furthermore,
plugging \( y=0 \) in the original equation
we get
\( f(x-c)-f(x)=cx+f(c)-1 \).
Since the range of the function (on \( x \))
on the right-hand side
is entire
\( \mathbb{R} \), we get \( \{f(x-c)-f(x)\,|\, x\in\mathbb{R}\}
=\mathbb R \), i.e.
\( A-A=\mathbb{R} \). Hence for every real number \( x \)
there are real numbers \( y_1,y_2\in A \) such that
\( x=y_1-y_2 \). Now we have
\[ f(x) = f(y_1-y_2)=
f(y_1-f(z))=
f(f(z))+y_1f(z)+f(y_1)-1\] \[ =
f(y_1)+f(y_2)+y_1y_2-1=c-\frac{x^2}{2}.\] From the original equation we easily get \( c=1 \). It is easy
to show that the function \( f(x)=1- \frac{x^2}{2} \)
satisfies the given equation.
Problem 17
First from \( f(x)=f(y) \)
we have
\( f^{(n)}(x)=f^{(n)}(y) \), hence \( f \) is injective.
The idea for what follows is clear once we look at the
graphical representation. Namely from the picture
it can be easily deduced that the function has to be
strictly increasing. Let us prove that formally.
Assume the contrary, that for some two real numbers
\( x_1< x_2 \)
we have \( f(x_1)\geq f(x_2) \). The continuity on \( [0,x_1] \)
implies that there is some
\( c \) such that \( f(c)=f(x_2) \),
which contradicts the injectivity of \( f \).
Now if \( x< f(x) \), we get \( f(x)< f(f(x)) \) etc.
\( x< f{(n)}(x)=x \). Similarly we get a contradiction
if we assume that \( x> f(x) \). Hence for each \( x\in[0,1] \) we
must have \( f(x)=x \).
Problem 18
Clearly \( f(x)= \frac 1x \)
is one solution to the functional equation. Let us prove that
the function is non-increasing. Assume the contrary that
for some \( 0< x< y \)
we have \( 0< f(x)< f(y) \).
We will consider the expression of the form
\( z= \frac{yf(y)-xf(x)}{y-x} \) since it is positive
and bigger then
\( f(y) \). We first plug \( (x,z-f(y)) \)
instead of \( (x,y) \) in the original equation, then we
plug \( z-f(x) \) instead of \( y \), we get \( x=y \),
which is a contradiction. Hence the function is
non-decreasing.
Let us prove that \( f(1)=1 \). Let \( f(1)\neq 1 \). Substituting \( x=1 \) we get \( f(f(1)+y)=f(1+y) \), hence \( f(u+|f(1)-1|)=f(u) \) for \( u> 1 \). Therefore the function is periodic on the interval \( (1,+\infty) \), and since it is monotone it is constant. However we then conclude that the left-hand side of the original equation constant and the right-hand side is not. Thus we must have \( f(1)=1 \). Let us prove that \( f(x)= \frac 1x \) for \( x> 1 \). Indeed for \( y=1- \frac 1x \) the given equality gives \( f\Big(f(x)- \frac 1x\Big)=xf(x) \). If \( f(x)> \frac 1x \) we have \( f\Big(f(x)- \frac 1x+1\Big)\leq f(1)=1 \) and \( xf(x)> 1 \). If \( f(x)< \frac 1x \) we have \( f\Big(f(x)- \frac 1x+1\Big)\geq f(1)=1 \), and \( xf(x)< 1 \). Hence \( f(x)= \frac 1x \). If \( x< 1 \), plugging \( y= \frac 1x \) we get \[ f\Big(f(x)+\frac 1x\Big)=xf(2)= \frac x2,\] and since \( \frac 1x\geq 1 \), we get \( f(x)+ \frac 1x= \frac 2x \), i.e. \( f(x)= \frac 1x \) in this case, too. This means that \( f(x)= \frac 1x \) for all positive real numbers \( x \).
Problem 19 (Bulgaria 1998)
The common idea for the problems
of this type is to prove that \( f(y)< 0 \) for some \( y> 0 \) which
will lead us to the obvious contradiction. We can also see that
it is sufficient to prove that
\( f(x)-f(x+1)\geq c> 0 \), for every \( x \) because the simple
addition gives \( f(x)-f(x+m)\geq mc \). For sufficiently large
\( m \) this implies \( f(x+m)< 0 \).
Hence our goal is finding \( c \) such that
\( f(x)-f(x+1)\geq c \),
for every \( x \).
Assume that such function exists.
From the given inequality we get
\( f(x)-f(x+y)\geq \frac{f(x+y)y}{f(x)} \) and the function
is obviously decreasing. Also from the given
equality we can conclude that
\[ f(x)-f(x+y)\geq \frac{f(x)y}{f(x)+y}.\]
Let \( n \) be a natural number such that
\( f(x+1)n\geq 1 \)
(such number clearly exists).
Notice that for \( 0\leq
k\leq n-1 \) the following inequality holds \[ f\Big(x+\frac
kn\Big)-f\Big(x+ \frac{k+1}{n}\Big)\geq\frac{f\Big(x+\frac
kn\Big)\frac 1n}{f\Big(x+\frac kn\Big)+\frac 1n}\geq
\frac{1}{2n},\] and adding similar realitions for all described
\( k \) yields \( f(x)-f(x+1)\geq \frac 12 \) which is a contradiction.
Problem 20
This is a typical problem in which the
numbers should be considered in some base different than 10.
For this situation the base \( 3 \) is doing the job.
Let us calculate \( f(n) \)
for \( n\leq 8 \) in an attempt to guess the solution. Clearly the
given equation can have only one solution.
\[ f((1)_3)=(2)_3,\; f((2)_3)=(1)_3,\; f((10)_3)=6=(20)_3,
\; f((11)_3)=8=(22)_3,\]
\[ f((12)_3)=7=(21)_3,\; f((20)_3)=3=(10)_3,\;
f((21)_3)=5=(12)_3,\; f((22)_3)=4=(11)_3.\]
Now we see that \( f(n) \) is obtained from \( n \)
by changing each digit \( 2 \) by \( 1 \), and conversely. This can
be now easily shown by induction.
It is clear that \( f(n)=2n \)
if and only if in the system with base
3 \( n \) doesn\( \prime \)t contain any digit \( 1 \) (because this would
imply \( f(n)< 2n \)). Now it is easy to count the number of
such \( n^{\prime} \)s. The answer is 127.
Problem 21 (BMO 2003, shortlist)
Notice that from (i) and (ii)
we conclude that \( f(x)> 0 \), for every rational
\( x \). Now (i) implies that for \( x=y=1 \) we get \( f(1)=0 \)
and similarly for \( x=y=-1 \)
we get \( f(-1)=1 \). By induction \( f(x)\leq 1 \) for every
integer \( x \). For \( f(x)\leq f(y) \) from
\( f\Big( \frac yx\Big)f(y)=f(x) \)
we have that \( f\Big( \frac yx\Big)\leq 1 \), and according
to (ii) \( f\Big( \frac
yx+1\Big)\leq 1. \) This implies \[ f(x+y)=f\Big( \frac
yx+1\Big)f(x)\leq f(x),\] hence
\( f(x+y)\leq \max \{f(x),f(y)\} \),
for every \( x,y\in\mathbb Q \).
Now you might wonder how did we get this idea. There is one
often neglected fact that for every two relatively prime
numbers \( u \) and \( v \),
there are integers \( a \) and \( b \) such that \( au+bv=1 \). What is
all of this good for? We got that \( f(1)=1 \), and we know that
\( f(x)\leq 1 \) for all \( x\in\mathbb{Z} \) and since
\( 1 \) is the maximum of the function on \( \mathbb{Z} \)
and since we have the previous inequality our goal
is to show that the value of the function is \( 1 \) for
a bigger class of integers. We will do this
for prime numbers. If for every prime \( p \) we have
\( f(p)=1 \) then \( f(x)=1 \) for every integer implying
\( f(x)\equiv 1 \) which contradicts (iii). Assume therefore that
\( f(p)\neq 1 \) for some \( p\in\mathbb{P} \). There are \( a \) and
\( b \) such that \( ap+bq=1 \) implying
\( f(1)=f(ap+bq)\leq\max\{f(ap),f(bq)\}. \) Now we must have
\( f(bq)=1 \) implying that \( f(q)=1 \) for every other prime number
\( q \). From (iii)
we have
\[ f\Big(\frac{2003}{2002}\Big)=\frac{f(2003)}{f(2)f(7)f(11)f(13)}=2,\]
hence only one of the numbers \( f(2),f(7),f(11),f(13) \)
is equal to \( 1/2 \). Thus \( f(3)=f(167)=f(2003) \) giving:
\[ f\Big(\frac{2004}{2003}\Big)=\frac{f(2)^2f(3)f(167)}
{f(2003)}=f(2)^2.\]
If \( f(2)=1/2 \) then \(
f\Big(\frac{2003}{2002}\Big)= \frac 14 \), otherwise it is \( 1 \).
It remains to construct one function for each of the given values. For the first value it is the multiplicative function taking the value \( 1/2 \) at the point \( 2 \), and \( 1 \) for all other prime numbers; in the second case it is a the multiplicative function that takes the value \( 1/2 \) at, for example, \( 7 \) and takes \( 1 \) at all other prime numbers. For these functions we only need to verify the condition (ii), but that is also very easy to verify.
Problem 22
The function of several variables appears in this problem.
In most cases we use the same methods as in the case
of a single-variable functions.
From the condition (ii) we get
\( f(1,0)=f(0,1)=0 \), and from (iii) we get
\( f(0,x)=f(x,0)=x^kf(1,0)=0 \). This means that \( f \) is
entirely defined on the edge of the region
\( G \). Assume therefore that \( 0< x\leq
y< 1 \). Notice that the condition (ii)
gives the value for one class
of pairs from \( G \) and that each pair in \( G \)
can be reduced to one of the members of the class.
This implies
\[ f(x,y)=f(y,x)=y^kf\Big(1,\frac xy\Big)=y^{k-1}x.\]
This can be written as
\( f(x,y)=\min(x,y)(\max(u,v))^{k-1} \) for all
\( 0< x,y< 1 \). Let us find all possible values for \( k \).
Let
\( 0< x\leq \frac 12\leq y< 1 \). From the condition (i),
and the already obtained results we get
\[ f\Big(f\Big(x, \frac 12\Big),y\Big)=f\Big(x\Big( \frac 12\Big)^{k-1},y\Big)=f\Big(x,f\Big( \frac 12\Big)\Big)=f\Big(x,\frac 12 y^{k-1}\Big).\]
Let us now consider \( x\leq 2^{k-1}y \)
in order to simplify the expression to the form
\( f\Big(x, \frac 12
y^{k-1}\Big)=x\Big(\frac y2\Big)^{k-1} \),
and if we take \( x \)
for which \( 2x\leq y^{k-1} \) we get \( k-1=(k-1)^2 \), i.e.
\( k=1 \) or \( k=2 \). For \( k=1 \) the solution is \( f(x,y)=\min(x,y) \),
and for
\( k=2 \) the solution is \( f(x,y)=xy \).
It is easy to verify that both solutions satisfy the
given conditions.
Problem 23 (APMO 1989)
Clearly every function of the form
\( x+d \) is the solution of the given equation. Another useful
idea appears in this problem. Namely denote by \( S_d \)
the the set of all numbers \( x \) for which
\( f(x)=x+d \). Our goal is to prove that
\( S_d=\mathbb{R} \). Assume that \( S_d \) is non-empty.
Let us prove that for \( x\in S_d \) we have \( x+d\in S_d \) as well.
Since \( f(x)=x+d \), according to the definition of the inverse
function we have \( g(x+d)=x \),
and the given equation implies \( f(x+d)=x+2d \), i.e.
\( x+d\in S_d \).
Let us prove that the sets \( S_{d^{\prime}} \) are empty, where \( d^{\prime}< d \).
From the above we have that each of those sets is
infinite, i.e. if \( x \) belongs to some of them, then
each \( x+kd \) belongs to it as well. Let us use this
to get the
contradiction. More precisely we want to prove that
if \( x\in S_d \) and
\( x\leq y\leq x+(d-d^{\prime}) \), then \( y\not\in S_{d^{\prime}} \).
Assume the contrary. From the monotonicity we have
\( y+d^{\prime}=f(y)\geq f(x)=x+d \), which is a contradiction
to our assumption. By further induction we prove that
every \( y \) satisfying
\[ x+k(d-d^{\prime})\leq y< x+(k+1)(d-d^{\prime}),\] can\( \prime \)t be a member of
\( S_{d^{\prime}} \).
However this is a contradiction
with the previously established
properties of the sets \( S_d \) and \( S_{d^{\prime}} \).
Similarly if \( d^{\prime}> d \) switching the roles of \( d \) and \( d^{\prime} \)
gives a contradiction.
Simple verification shows that each \( f(x)=x+d \) satisfies the given
functional equation.
Problem 24
Notice that we have both
\( h(h(n)) \) and
\( h(n+1) \), hence it is not possible to form a
recurrent equation. We have to use another approach
to this problem. Let us first calculate
\( h(1) \) and \( h(2) \). Setting \( n=1 \) gives \( h(h(1))+h(2)=3 \),
therefore \( h(h(1))\leq 2 \) and \( h(2)\leq 2 \).
Let us consider the two cases:
Problem 25 (IMO 2004, shortlist)
Let us make the substitution \( z=x+y \), \( t=xy \). Given \( z,t\in
\mathbb{R} \), \( x,y \) are real if and only if \( 4t\leq z^2 \). Define
\( g(x)=2(f(x)-x) \). Now the given functional equation transforms into
\[ f\left(z^2+g(t)\right)=\left(f(z)\right)^2\;\;
\mbox{for all }\;
t,z \in\mathbb{R}\;\mbox{ with }\;z^2\geq 4t.\quad\quad\quad\quad\quad (1)
\] Let us set
\( c=g(0)=2f(0) \). Substituting \( t=0 \) into (1)
gives us
\[ f(z^{2}+c)=\left(f(z)\right)^2\;\mbox{ for all }\;
z\in\mathbb{R}. \quad\quad\quad\quad\quad (2)\] If \( c< 0 \), then taking \( z \) such that
\( z^2+c=0 \), we obtain from (2) that \( f(z)^2=c/2 \), which is
impossible; hence \( c\geq0 \). We also observe that
\[ x> c\;\;\mbox{
implies }\;\; f(x)\geq0. \quad\quad\quad\quad\quad (3)\]
If \( g \) is a constant function,
we easily find that \( c=0 \) and therefore \( f(x)=x \),
which is indeed
a solution.
Suppose \( g \) is nonconstant, and let \( a,b\in\mathbb{R} \) be such that \( g(a)-g(b)=d> 0 \). For some sufficiently large \( K \) and each \( u,v\geq K \) with \( v^2-u^2=d \) the equality \( u^2+g(a)=v^2+g(b) \) by (1) and (2) implies \( f(u)=f(v) \). This further leads to \( \ g(u)-g(v)=2(v-u)= \frac d{u+\sqrt{u^2+d}} \). Therefore every value from some suitably chosen segment \( [\delta,2\delta] \) can be expressed as \( g(u)-g(v) \), with \( u \) and \( v \) bounded from above by some \( M \). Consider any \( x,y \) with \( y> x\geq 2\sqrt{M} \) and \( \delta< y^2-x^2< 2\delta \). By the above considerations, there exist \( u,v\leq M \) such that \( g(u)-g(v)=y^2-x^2 \), i.e., \( x^2+g(u)=y^2+g(v) \). Since \( x^2\geq4u \) and \( y^2\geq 4v \), (1) leads to \( f(x)^2=f(y)^2 \). Moreover, if we assume w.l.o.g. that \( 4M\geq c^2 \), we conclude from (3) that \( f(x)=f(y) \). Since this holds for any \( x,y\geq 2\sqrt{M} \) with \( y^2-x^2\in[\delta, 2\delta] \), it follows that \( f(x) \) is eventually constant, say \( f(x)= k \) for \( x\geq N=2\sqrt{M} \). Setting \( x> N \) in (2) we obtain \( k^2=k \), so \( k=0 \) or \( k=1 \). By (1) we have \( f(-z)=\pm f(z) \), and thus \( |f(z)|\leq 1 \) for all \( z\leq-N \). Hence \( g(u)=2f(u)-2u\geq-2-2u \) for \( u\leq-N \), which implies that \( g \) is unbounded. Hence for each \( z \) there exists \( t \) such that \( z^2+g(t)> N \), and consequently \( f(z)^2=f(z^2+g(t))=k=k^2 \). Therefore \( f(z)=\pm k \) for each \( z \). If \( k=0 \), then \( f(x)\equiv0 \), which is clearly a solution. Assume \( k=1 \). Then \( c=2f(0)=2 \) (because \( c\geq 0 \)), which together with (3) implies \( f(x)=1 \) for all \( x\geq2 \). Suppose that \( f(t)=-1 \) for some \( t< 2 \). Then \( t-g(t)=3t+2> 4t \). If also \( t-g(t)\geq0 \), then for some \( z\in\mathbb{R} \) we have \( z^2=t-g(t)> 4t \), which by (1) leads to \( f(z)^2=f(z^2+g(t))=f(t) =-1 \), which is impossible. Hence \( t-g(t)< 0 \), giving us \( t< -2/3 \). On the other hand, if \( X \) is any subset of \( (-\infty,-2/3) \), the function \( f \) defined by \( f(x)=-1 \) for \( x\in X \) and \( f(x)=1 \) satisfies the requirements of the problem. To sum up, the solutions are \( f(x)=x \), \( f(x)=0 \) and all functions of the form \[ f(x)=\left\{\begin{array}{ll} 1, &x\not \in X,\\ -1,& x\in X, \end{array}\right.\] where \( X\subset(-\infty,-2/3) \). |
2005-2018 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |