Why can't we just write down an FE?

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Why can't we just write down an FE?

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: CAMO 2022/2 (https://aops.com/community/c594864h2791269p24548889)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#1 h Mar 20, 2022, 7:10 AM • 3 Y

Y by goodbear, jasperE3, cubres

Find all functions $f:\mathbb Z\to\mathbb Z$ such that $f(f(x)f(y))=f(xf(y))+f(y)$ for all integers $x$ and $y$ .

Proposed by nukelauncher and TheUltimate123

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

558 posts

#2 h Mar 20, 2022, 7:10 AM • 3 Y

Y by lazizbek42, PRMOisTheHardestExam, cubres

Note that by switching the variables $x,y$ we infer $f(xf(y))+f(y)=f(yf(x))+f(x)$ and so by taking $y=0$ here we get $f(xf(0))=f(x)$ . We will use this relation multiple times without any further mentioning. As a corollary, $f(f(0))=f(1)$ .

Taking $x=0$ and switching $y$ to $x$ in the given we obtain $f(f(x))=f(x)+f(0)$ .
Note that $f(0)+f(1)=f(f(1))=f(f(1)f(0))=f(f(0))+f(0)=f(0)+f(0)+f(0)=3f(0),$ so $f(1)=2f(0)$ .

Taking $x \rightarrow f(x)$ in $f(xf(y))+f(y)=f(yf(x))+f(x)$ and using that $f(f(x))=f(x)+f(0)$ we infer that

$f(yf(x))+f(y)=f(y(f(x)+f(0))+f(0)$
Take $y=1$ in the above to obtain

$f(f(x))+f(0)=f(f(x)+f(0))$
Now, taking $x=0$ here we have $f(2)=3f(0)$ . Taking $x=1$ we have $f(3)=4f(0)$ , and so we may keep going on. Thus, we have $f(k)=(k+1)f(0)$ for all $k \geq 0$ .

For the negative $k$ 's, we take $y=-1$ in $f(yf(x))+f(y)=f(y(f(x)+f(0))+f(0)$ to obtain

$f(-f(x)-f(0))=f(-f(x))+f(-1)-f(0),$
and since we know $f(k)=(k+1)f(0)$ for $k \geq 0$ we may successively take $x$ to be any positive integer, and so we have $f(-k)=kf(-1)-(k-1)f(0)$ for all $k \leq 0$ .

To sum up what we already have, if we let $f(0)=a$ and $f(-1)=b$ , we have $f(x)=\begin{cases}a(x+1)&x\geq 0\\a(x+1)-bx&x <0 \end{cases}$

Now, we will take cases regarding the values of $a,b$ .

If $a \geq 0$ , then $a(a+1)=f(a)=f(f(0))=2f(0)=2a,$ and so $a \in \{0,1 \}$

If $a=0$ then $f(x)=f(xf(0))=f(0)=0$ and so $f$ is the zero function, which evidently works.
If $a=1$ then $f(x)=\begin{cases}x+1&x\geq 0\\x+1-bx&x <0 \end{cases}$ .

If $b \leq 0$ then $x+1-bx<0$ for all $x<0$ , and so taking $x,y<0$ we have

$f((x+1-xb)(y+1-yb))=f(x(y+1-yb))+(y+1-yb),$
and so

$(x+1-xb)(y+1-yb)+1=x(y+1-yb)+1+(y+1-yb),$
hence

$bx(y+1-yb)=0$
for all $x,y<0$ , thus $b=0$ , which in turn gives $f(x)=x+1$ for all $x$ , which works.

If $b>0$ then $x+1-xb>0$ for $x<0$ , hence if we take $x,y<0$ we have

$f((y+1-yb)(x+1-xb))=f(x(y+1-yb))+(y+1-yb),$
and so

$(y+1-yb)(x+1-xb)+1=(1-b)x(y+1-yb)+1+(y+1-yb),$
which is always true.

If we take $x,y>0$ we can easily check that we are okay. If now $x>0>y$ , then we have

$f((x+1)(y+1-yb))=f(x(y+1-yb))+(y+1-yb),$
and so

$(x+1)(y+1-yb)+1=x(y+1-yb)+1+(y+1-yb),$
which is always true.

Lastly, if $y>0>x$ , then we have

$f((y+1)(x+1-xb))=f(x(y+1))+(y+1),$
and so

$(y+1)(x+1-xb)+1=(1-b)(xy+x)+1+(y+1),$
which is also always true.

Thus, we have the solution $f(x)=\begin{cases}x+1&x\geq 0\\x+1-bx&x <0 \end{cases}$ , where $b \geq 0$ .

On the other hand, if $a<0$ , then $2a=f(a)=a^2+a-ab$ and so $a=0$ or $b=a-1$ . As we saw before the former implies $f$ is the zero function. If $b=a-1$ , then $f(x)=\begin{cases}(x+1)a&x\geq 0\\x+a&x <0 \end{cases}$ .

We now take $x,y>0$ and we have

$f((x+1)(y+1)a^2)=f(x(y+1)a)+(y+1)a$
and so

$((x+1)(y+1)a^2+1)a=x(y+1)a+a+(y+1)a,$
hence

$(x+1)(y+1)(a-1)(a+1)=0,$
and so $a=-1$ . It is easy to verify that $f(x)=\begin{cases}-x-1&x\geq 0\\x-1&x <0 \end{cases}$ works.

Therefore, we have four solutions, namely the zero function, $f(x)=x+1$ , $f(x)=\begin{cases}x+1&x\geq 0\\x+1-bx&x <0 \end{cases}$ , where $b \geq 0$ and $f(x)=\begin{cases}-x-1&x\geq 0\\x-1&x <0 \end{cases}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

800 posts

#3 h Mar 20, 2022, 8:17 AM • 2 Y

Y by PRMOisTheHardestExam, cubres

CAMO P2

19 pages, 10 to 15 MOHS?

This post has been edited 1 time. Last edited by rama1728, Mar 20, 2022, 8:24 AM
Reason: O

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

71 posts

#4 h Aug 12, 2022, 2:24 PM • 2 Y

Y by PRMOisTheHardestExam, cubres

Let $P(x, y)$ denote the assertion: $f(f(x)f(y))=f(xf(y))+f(y)$

$P(0, x): f(f(0)f(x)) = f(x) + f(0)$
$P(x, 0): f(f(0)f(x)) = f(xf(0)) + f(0)$

The above two equations give us $f(xf(0)) = f(x)... (\spadesuit)$ which in turn transforms the first equation to: $f(f(x)) = f(x) + f(0)...(\clubsuit)$
Using this and inducting, we get $f(nf(0)) = (n+1)f(0)$ for all $n \ge 0 \implies \boxed{f(n) = f(nf(0)) = (n+1)f(0)}$ for all $n \ge 0$ .

Now for a nonnegative $n$ , $P(-1, n):$ $f(f(n)f(-1)) = f(-f(n)) + f(n) \implies f((n+1)f(0)f(-1)) = f(-(n+1)f(0)) + (n+1)f(0)$ .
By $(\spadesuit)$ , $f((n+1)f(-1)) = f(-(n+1)) + (n+1)f(0)$ . So for a positive $n$ , $f(nf(-1)) = f(-n) + nf(0)$

Similarly, $P(n, -1):$ $f(f(n)f(-1)) = f(nf(-1)) + f(-1) \implies f((n+1)f(-1)) = f(nf(-1)) + f(-1)$ which by induction yields: $f(nf(-1)) = nf(-1) + f(0)$ due to the base case $f(f(-1)) = f(-1) + f(0)...(\clubsuit)$

Combining the last two results, we get $f(-n) + nf(0) = nf(-1) + f(0) \implies f(-n) = nf(-1) + (1-n)f(0)$

For the finish, we take two cases: $f(0) > 0$ or $f(0) < 0$ .

$\text{CASE 1: } f(0)>0$

By $(\spadesuit)$ , we have that $f(f(0)) = f(1) = 2f(0)$ but $f(f(0)) = [f(0) + 1]f(0)$ . Putting these together, $f(0)^2 + f(0) = 2f(0) \implies f(0) = 0, 1$

If $f(0) = 0$ , $P(0, x)$ gives us $f(x) = 0$ for all integers $x$ .
If $f(0) = 1$ , $f(n) = n+1$ for all positive $n$ and $f(-n) = nf(-1) + 1-n$ for all positive $n$ . If $f(-1) < 0$ , $P(-1, -1)$ gives $f(f(-1)^2) = f(-1) + f(-f(-1))$ $\implies f(-1)^2 + 1 = f(-1) + (-f(-1) + 1)$ $\implies f(-1)^2 = 0$ CONTRADICTION!

Therefore, $f(-1) \ge 0$ and it can be easily verified that all such functions $f(x)=\begin{cases}x+1&x\geq 0\\x+1-cx&{x <0, c \ge 0} \end{cases}$ work.

$\text{CASE 2: } f(0)<0$

Note that $(\spadesuit) \implies f(f(0)) = f(1) = 2f(0) \implies -f(0)f(-1) + (1+f(0))f(0) = 2f(0)$ as $f(0)$ is negative. This means $f(0) - f(-1) = 1 \implies f(-n) = f(0)-n[f(0)-f(-1)] = f(0)-n$ . Putting this back in $P(x, y)$ and doing some manipulations gives $f(0) = -1$ .
Thus we get another class of functions: $f(x)=\begin{cases}-x-1&x\geq 0\\x-1&x <0 \end{cases}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#5 h Aug 19, 2022, 8:26 AM • 1 Y

Y by cubres

Let $P(x,y)$ denote the equation $f(f(x)f(y))=f(xf(y))+f(y)$ for all integers $x,y.$

$P(x,0)-P(0,x)$ yields $f(xf(0))=f(x).$ Subtracting $f(f(x)f(0))=f(f(x))$ from $P(0,x)$ yields $f(f(x))=f(x)+f(0).$ Setting $x=0,f(0),f(f(0))$ etc. here imply, $f(xf(0))=(x+1)f(0)$ for $x\geq 0.$ Hence $f(x)=(x+1)f(0)$ for all $x\geq 0.$ Then $P(f(x),-1)-P(-1,f(x))$ implies $f(-x)=xf(-1)-(x-1)f(0).$

Subtracting $f(f(0)^2)=(f(0)^2+1)f(0)$ from $P(0,0)$ yields $f(0)\in{\pm 1,0}.$ If $f(0)=0,$ then $P(x,0)$ gives $f(x)=0$ for all $x$ ; it obviously works.

If $f(0)=1,$ then $f(-1)=2$ and so $f(x)=f(-x)=-x-1$ for $x\geq 0$ ; it is easy to see it works as well.

If $f(0)=-1,$ then $f(x)=x+1$ for $x\geq 0$ which works; and $f(-x)=-x-1+xf(-1).$ If $f(-1)\leq 0$ then $P(-x,-y)$ gives $f(-1)=0.$ Conversely, it is easy to check all such functions with $f(-1)\geq 0$ work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11352 posts

#6 h Apr 13, 2025, 6:01 AM • 1 Y

Y by cubres

TheUltimate123 wrote:

Find all functions $f:\mathbb Z\to\mathbb Z$ such that $f(f(x)f(y))=f(xf(y))+f(y)$ for all integers $x$ and $y$ .

Proposed by nukelauncher and TheUltimate123

nice

We claim that the solutions are $0$ , $-|x|-1$ , and $\begin{cases}x+1&\text{if }x\ge0\\cx+1&\text{if }x<0\end{cases}$ for any constant $c\le1$ (in particular, $c=1$ gives the solution $f(x)=x+1$ ).
To test that these work, $f\equiv0$ is routine, and $f\equiv-|x|-1$ is routine using the rules governing $|x|$ . To show that $\begin{cases}x+1&\text{if }x\ge0\\cx+1&\text{if }x<0\end{cases}$ works, we test $c=1$ and $c\le0$ separately. If $c=1$ then $f(x)=x+1$ fits. If $c\le0$ , then $cx+1\ge0$ for $x<0$ , so $f(x)\ge0$ for all $x$ . Then we have:
$f(f(x)f(y))=f(x)f(y)+1$ so if $x\ge0$ we have $xf(y)\ge0$ and so:
$f(f(x)f(y))=(x+1)f(y)+1=xf(y)+1+f(y)=f(xf(y))+f(y)$ and if $x<0$ we have $xf(y)<0$ and so:
$f(f(x)f(y))=(cx+1)f(y)+1=cxf(y)+1+f(y)=f(xf(y))+f(y).$

Now we prove that these are the only solutions.
First we find $f$ for positive values, a brief detour to calculate $f(0)$ , then we pin down the negative values.

Claim: $f(n)=(n+1)f(0)$ for all $n\ge0$
From setting $x=0$ and $y=0$ we have the following:
$f(f(y)f(0))=f(y)+f(0)$ and
$f(f(x)f(0))=f(xf(0))+f(0),$ and so (comparing) we get $f(xf(0))=f(x)$ . Then these equations each reduce to $f(f(x))=f(x)+f(0)$ .
If $f(n)=(n+1)f(0)$ for some $n\ge0$ (it obviously holds for the base case $n=0$ ) we have:
$f(n+1)=f((n+1)f(0))=f(f(n))=f(n)+f(0)=(n+1)f(0)+f(0)=(n+2)f(0).$
Claim: $f(0)=1$ (if $f$ is not one of the aforementioned functions)
For $x\ge0$ we have $xf(0)^2\ge0$ , so:
$\left(xf(0)^2+1\right)f(0)=f\left(xf(0)^2\right)=f(xf(0))=f(x)=(x+1)f(0)$ which gives $f(0)\in\{-1,0,1\}$ .
If $f(0)=0$ , from $f(x)=f(xf(0))$ we have $\boxed{f(x)=0}$ for all $x\in\mathbb Z$ .
If $f(0)=-1$ , we have $f(x)=f(-x)$ so $f(n)=f(-n)=-n-1$ for all $n\ge0$ , that is, $\boxed{f(x)=-|x|-1}$ .
Otherwise, $f(0)=1$ , which gives $f(f(x))=f(x)+1$ .

Claim: $f(n)=n(1-f(-1))+1$ for all $n<0$
From $P(y,x-1)$ for $x\ge1$ we have:
$f(xf(y))=f(xy)+x.$ Now we can show by induction that $f(xf(y)+nx)=f(xy)+(n+1)x$ for all $n\ge0$ : it's obviously true for $n=0$ and if it's true for some $n$ we have:
$f(x(f(y)+1)+nx)=f(xf(f(y))+nx)=f(xf(y))+(n+1)x=f(xy)+(n+2)x$ so $f(xf(y)+(n+1)x)=f(xy)+(n+2)x$ .
Now for any $y$ , choose some large $n\gg|f(y)|$ such that $xf(y)+nx\ge0$ , we have:
$f(xy)+(n+1)x=f(xf(y)+nx)=xf(y)+nx+1,$ taking $y=-1$ this gives $f(-x)=xf(-1)-x+1$ for all $x\ge1$ which rearranges into what we wanted.

Finish: $f(-1)\ge0$
Suppose $f(-1)<0$ , then $xf(-1)-x+1<0$ for all $x\ge1$ , so using $f(f(x))=f(x)+1$ we have:
$xf(-1)-x+2=1+f(-x)=f(f(-x))=f(xf(-1)-x+1)=xf(-1)-x+2-f(-1)(xf(-1)-x+1),$ and (simplifying) we get $xf(-1)-x+1=0$ for all $x\ge1$ , impossible (for instance take $x=2$ ).
So if we let $c=1-f(-1)$ we get $\boxed{f(x)=\begin{cases}x+1&\text{if }x\ge0\\cx+1&\text{if }x<0\end{cases}}$ where $c\le1$ is any constant.

This post has been edited 1 time. Last edited by jasperE3, Apr 13, 2025, 3:49 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a