Skip to main content

Functional Equations 101

Let's get to the math: 

Let there be two sets $X$ and $Y$. A function from $X$ to $Y$ denoted as $f \colon X \to Y$ is assigning a value in $Y$ for every element in $X$. We say that $X$ is the domain of the function $f$ and $Y$ is the range. 

A function $f \colon X \to y$ is said to be injective if $f(x) = f(x^{\prime}) \implies x = x^{\prime}$ To put it in a more abstract way, if there is some $a \in Y$ then there is at most one $b \in X$ such that $f(b) = a$ holds true. 

A function is said to be surjective when for any $a \in Y$ there is at least one $b \in X$ such that $f(b) = a$ holds true. 

A function is bijective if for every $a \in Y$ there is exactly one $b \in X$ such that $f(b) = x$. Bijective functions are basically functions which are both injective and surjective. 

Bonus: A function $f \colon X \to X$ is known as an involution if $f(f(x)) = x \; \forall  x \in X$ 
As an exercise, the readers should try to prove that every function that is an involution is a bijective function as well.  

Let's look at some problems now: 

Problem 1: (IMO 2019) Let $\mathbb{Z}$ be the set of integers. Determine all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that, for all integers $a$ and $b$, $$f(2a)+2f(b)=f(f(a+b)).$$

Solution: The answers are $f(x)=0$ and $f(x)=2x+d$ for some $d$. 
Note that $$f(2)+2f(b) = f(f(b+1)) = f(0)+2f(b+1) \implies f(b+1)-f(b)=\frac{f(2)-f(0)}{2}.$$ This means $f$ is linear, so let $f(x)=cx+d$. We have that $$c(2a)+d+2(cb+d)=c(c(a+b)+d)+d \iff c(2a+2b)+2d = c^2(a+b)+cd,$$ which is true if the coefficients of the monomials line up, or $2c=c^2$ and $cd=2d$. From the first equation, $c=0$ or $c=2$. $c=0$ gives that $d=0$ and the solution $f(x)=0$ and $c=2$ gives that $d$ can be anything and the solution $f(x)=2x+d$. 

Problem 2:: (JMO 2021) Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for positive integers $a$ and $b,$ $$f(a^2 + b^2) = f(a)f(b) \text{ and } f(a^2) = f(a)^2$$

Solution: We claim that $f(x)=1$ is the only solution. Since $f(1^2)=f(1)^2$, this means that $f(1)=1$. We also have $f(1^2+1^2)=f(1)f(1)=1$, so $f(2)=1$. Suppose that there exists another solution. Then, we must have $f(k)\neq1$ for some $k$. Consider the smallest value of $k$. Then, $f(x)=1$ for all $x<k$. We will prove that this is impossible.

Case 1: $k$ is even
Then, substituting $a=2x$ and $b=x^2-1$, we get

$$f((2x)^2+(x^2-1)^2)=f(2x)f(x^2-1)$$
$$f((x^2+1)^2)=f(2x)f(x^2-1)$$
$$f(x^2+1)^2=f(2x)f(x^2-1)$$
$$f(x)^2f(1)^2=f(2x)f(x^2-1)$$
$$f(x)^2=f(2x)f(x^2-1)$$
Now, let $x=\frac k2$. Since $k\geq4$, we have $x\geq2$, so $a,b>0$. Since $x<k$, this gives
$$f(k)f(x^2-1)=1,$$ so since $f(k)$ is a positive integer, this means that $f(k)=1$, which is a contradiction.

Case 2: $k$ is odd
Substituting $a=2x(x+1)$ and $b=(x+1)^2-x^2=2x+1$, we get

$$f((2x(x+1))^2+((x+1)^2-x^2)^2)=f(2x(x+1))f(2x+1)$$
$$f(((x+1)^2+x^2)^2)=f(2x(x+1))f(2x+1)$$
$$f((x+1)^2+x^2)^2=f(2x(x+1))f(2x+1)$$
$$f(x+1)^2f(x)^2=f(2x(x+1))f(2x+1)$$
Now, let $x=\frac{k-1}2$. Since $k\geq3$, we have $x\geq1$, so $x+1<2x+1$ and $a,b>0$. Therefore, we have $$f(2x(x+1))f(k)=1,$$ so $f(k)=1$.

Since $f(x)=1$ obviously works, this means that the only function that satisfies the conditions is $\boxed{f(x)=1}$ for all $x\in\mathbb N$. 


Problem 3: (IMO 2010) Find all function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that for all $x,y\in\mathbb{R}$ the following equality holds:
$$f(\left\lfloor x\right\rfloor y)=f(x)\left\lfloor f(y)\right\rfloor$$ where $\left\lfloor a\right\rfloor $ is greatest integer not greater than $a.$ 

Solution: Let $x=1$. We can see that $$f(y)=f(1)\lfloor f(y)\rfloor.$$ If $f(1)=0$, we know that all $f(y)=0$, which we will check later. Plugging the equation into the original equation, $$f(1)f(\lfloor x\rfloor y)=f(x)f(y).$$ However, if we switched the order of $x$ and $y$, we would get that $$f(\lfloor x\rfloor y)=f(\lfloor y\rfloor x).\; (1)$$ Now, for all $y$ such that $y>0$, plug $$\left(\frac{y}{\lfloor y\rfloor+1},\lfloor y\rfloor +1\right)$$ into (1). We get that $$f(0)=f\left(\left(\lfloor y\rfloor+1\right) x\right)=f(y).$$ This means that $f(y)$ is constant for all nonnegative $y$. For all $y$ such that $y<0$, plug $$\left(\frac{y}{\lfloor y\rfloor-1},\lfloor y\rfloor -1\right)$$ into (1). We get that $$f(0)=f\left(\left(\lfloor y\rfloor-1\right) x\right)=f(y).$$ This means that $f(y)$ is constant for all nonpositive $y$. Therefore, we can conclude that $f(x)$ is constant. The previous $f(x)=0$ also follows this, so just let $f(x)=C$. We have that $C=C\lfloor C\rfloor$, so $C=0$ or $\lfloor C\rfloor=1$. Both of these clearly work, so we have our answer: $f(x)=C$ where $C$ can either be $0$ or have a floor of $1$.

Problem 4: (IMO 2008) Find all functions $ f: (0, \infty) \mapsto (0, \infty)$ (so $ f$ is a function from the positive real numbers) such that
$$ \frac {\left( f(w) \right)^2 + \left( f(x) \right)^2}{f(y^2) + f(z^2) } = \frac {w^2 + x^2}{y^2 + z^2}$$
holds for all positive real numbers $ w,x,y,z,$ satisfying $ wx = yz$

Solution: We claim the only solutions are $f(x)=x$ and $f(x)=\frac1x$.
Plugging in $w=x=y=z$, we get
$$\frac{2f(w)^2}{2f(w^2)}=\frac{2w^2}{2w^2}=1$$
$$f(w)^2=f(w^2)$$
It follows that $f(1)=1$.
In addition, if $wx=yz$, then
$$\frac {f(w^2) + f(x^2)}{f(y^2) + f(z^2) } = \frac {w^2 + x^2}{y^2 + z^2}.$$
Let $ab=cd$. Plugging in $w=\sqrt{a}$, $x=\sqrt{b}$, $y=\sqrt{c}$, $z=\sqrt{d}$, we get
$$\frac {f(a) + f(b)}{f(c) + f(d) } = \frac {a + b}{c + d}.$$
Let $ab=c^2$. Then, we have
$$\frac{f(a)+f(b)}{2f(c)}=\frac{a+b}{2c}$$
$$\frac{f(a)+f(b)}{a+b}=\frac{f(c)}{c}$$
Let $a=1$, $c=\sqrt{b}$, and $b\neq 1$. We get
$$\frac{f(1)+f(b)}{1+b}=\frac{f(\sqrt{b})}{\sqrt{b}}$$
$$\frac{1+f(b)}{1+b}=\frac{f(\sqrt{b})}{\sqrt{b}}$$
$$\frac{(1+f(b))^2}{(1+b)^2}=\frac{f(b)}{b}$$
This is a quadratic in $f(b)$. We can check that $f(b)=\frac1b$ and $f(b)=b$ both satisfy this equation. Since $b\neq 1$, these are distinct, so these are the only solutions, so there are no other possible values of $f(b)$.

Let $c\neq 1$. There are 2 cases.

Case 1: $f(c)=c$
Then, for all $a, b$ such that $ab=c^2$, we have
$$\frac{f(a)+f(b)}{a+b}=\frac{f(c)}{c}=1$$
If $f(a)=a$, then $f(b)=b$.
Assume towards a contradiction that $f(a)=\frac1a$ and $f(b)=\frac1b$. Then,
$$\frac1a+\frac1b=a+b$$
$$\frac{a+b}{ab}=a+b$$
$$ab=1$$
Then, $c=1$, a contradiction. So, we have $f(a)=a$ and $f(b)=b$. So, $f(x)\equiv x$.

Case 2: $f(c)=\frac1c$
Then, for all $a, b$ such that $ab=c^2$, we have
$$\frac{f(a)+f(b)}{a+b}=\frac{f(c)}{c}=\frac1{c^2}=\frac1{ab}$$
$$f(a)+f(b)=\frac{a+b}{ab}=\frac1a+\frac1b$$
If $f(a)=\frac1a$, then $f(b)=\frac1b$. Assume towards a contradiction $f(a)=a$ and $f(b)=b$. Then,
$$a+b=\frac1a+\frac1b$$
$$ab=1$$
Then, $c=1$, a contradiction. so, we have $f(a)=\frac1a$ and $f(b)=\frac1b$. So, $f(x)\equiv \frac1x$.

Problem 5: (Shortlist 2018) Let $\mathbb{Q}_{>0}$ denote the set of all positive rational numbers. Determine all functions $f:\mathbb{Q}_{>0}\to \mathbb{Q}_{>0}$ satisfying $$f(x^2f(y)^2)=f(x)^2f(y)$$ for all $x,y\in\mathbb{Q}_{>0}$

Solution: The answer is $\boxed{f\equiv 1}$, which obviously works.
Let $P(x,y)$ be the assertion. Suppose that $f(1)=c$. Then $P(1,1)$ gives that $f(c^2)=c^3$ and $P(1,c^2)$ gives $f(c^6)=c^5$. But also $P(c^2, 1)$ gives $f(c^6)=c^7$ which implies that $f(1)=1$. Then $P(1, x)$ and $P(x, 1)$ give
$$f(f(x)^2)=f(x)$$
$$f(x^2)=f(x)^2$$
or that $f(x)=f(f(x)^2)=f(f(x))^2$. Then $f(x)$ is a $2^n$th power for arbitrarily large $n$, implying that $\boxed{f\equiv 1}$, and we are done. 

Problem 6: (EGMO 2021) Find all functions $f:\mathbb{Q}\to\mathbb{Q}$ such that the equation
$$f(xf(x)+y) = f(y) + x^2$$ holds for all rational numbers $x$ and $y$.

Solution: Let $P(x,y)$ denote the assertion that $$f(xf(x)+y) = f(y) + x^2.$$

Lemma 1: $f$ is surjective. 
Proof: $P(x,0): f(xf(x))=f(0)+x^2$. 

$P(x,-xf(x)): f(0)=f(-xf(x))+x^2$, so $f(-xf(x))=f(0)-x^2$. 

Thus, by induction, $f(0)+kx^2$ for any integer $k$ is in the image of $f$. 

But note that $\frac{p}{q}=pq\left(\frac{1}{q}\right)^2$, so $f(0)+\frac{p}{q}$ is in the image of $f$, for any integers $p,q$, where $q\ne 0$. 

Thus, any rational number is in the image of $f$. $\blacksquare$

Lemma 2: $f(0)=0$. 
Suppose $f(k)=0$ (a such $k$ must exist as $f$ is surjective). 

$P(k,x): f(x)=f(x)+k^2\implies k=0$. 


Lemma 3: $f(1)=\{-1,1\}$. 
$P(1,0): f(f(1))=1$. 

$P(f(1),0): f(f(1))=f(1)^2$. 

This implies $f(1)^2=1$, which proves our claim. 


Case 1: $f(1)=1$. 
Then $P(1,x): f(x+1)=f(x)+1\implies f(x)=x\forall x\in\mathbb{Z}$. 

We claim that $f(kxf(x))=kx^2$ for all positive integers $k$. 
Proof: We proceed by induction. Setting $y=0$ gives $f(xf(x))=x^2$. Now suppose for all positive integers $l$ less than $k$, $f(lxf(x))=lx^2$. 

$P(x,(k-1)xf(x)): f(kxf(x))=(k-1)x^2+x^2=kx^2$, which completes the induction. 


For any rational $x$, we take a positive integer $k$ so that $kxf(x)$ is an integer (this is obviously always possible). 

So $kxf(x)=kx^2\implies xf(x)=x^2\implies \boxed{f(x)=x\forall x\in\mathbb{Q}}$. 


Case 2: $f(1)=-1$. 
$P(1,x): f(x-1)=f(x)+1$. 

So for all integers $n$, $f(n)=-n$. 

We claim that $kxf(x)=kx^2$ for all positive integers $k$. 
Proof: Same as above case. 


For any given $x$, take a positive integer $k$ so that $kxf(x)$ is an integer. 

Then $-kxf(x)=kx^2\implies -xf(x)=x^2\implies \boxed{f(x)=-x\forall x\in\mathbb{Q}}$

Bratin. 

Comments

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig