integer functional equation

The post below has been deleted. Click to close.

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

1963 posts

#1 h Jul 7, 2016, 7:52 PM • 30 Y

Y by mathmaths, doxuanlong15052000, Davi-8191, tenplusten, mathleticguyyy, Amir Hossein, A-Thought-Of-God, MathLuis, mathematicsy, chessgocube, HWenslawski, centslordm, donotoven, megarnie, jhu08, RedFlame2112, ImSh95, vic_52math, OronSH, Adventure10, Mango247, kimyager, lian_the_noob12, ItsBesi, WiseTigerJ1, Sedro, aidan0626, cubres, ray66, Funcshun840

Determine all functions $f:\mathbb{Z}\rightarrow\mathbb{Z}$ with the property that $f(x-f(y))=f(f(x))-f(y)-1$ holds for all $x,y\in\mathbb{Z}$ .

Z K Y

The post below has been deleted. Click to close.

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

Kezer

986 posts

Kezer

#2 h Jul 7, 2016, 8:05 PM • 10 Y

Y by Vietjung, Plops, chessgocube, HWenslawski, centslordm, donotoven, megarnie, lego_man, Adventure10, WiseTigerJ1

That was also Problem 5 in this year's German TSTST (VAIMO).

Z K Y

The post below has been deleted. Click to close.

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

Aiscrim

409 posts

Aiscrim

#6 h Jul 7, 2016, 8:15 PM • 9 Y

Y by baladin, A-Thought-Of-God, chessgocube, centslordm, donotoven, megarnie, Adventure10, gatnghiep, WiseTigerJ1

The only functions that work are $f\equiv -1$ and $f(x)=x+1,\ \forall x\in \mathbb{Z}$ .

Let $P(x,y)$ be the assertion that $f(x-f(y))=f(f(x))-f(y)-1$ . From $P(x,f(x))$ , we get that there is an $a\in \mathbb{Z}$ s.t. $f(a)=-1$ . From $P(x,a)$ we get $f(x+1)=f(f(x))$ , so $f(f(f(x)))=f(f(x+1))=f(x+2)$ .

$P(f(x),x)$ yields $f(0)=f(f(f(x)))-f(x)-1\Leftrightarrow f(x+2)=f(x)+f(0)+1$ . It's easy to show by induction that $f(2k)=f(0)+k(f(0)+1)\ (*)$

Looking at $P(f(8),f(4))$ and using $(*)$ , we get $f(2f(0)+2)=3f(0)+2$ . As $2f(0)+2$ is even we can use again $(*)$ to get $f(0)\in \{-1,1\}$ .

If $f(0)=-1$ , by $(*)$ and induction we get $f(2k)=-1,\ \forall k\in \mathbb{Z}$ . Also note $f(2k+1)=f(f(2k))=f(-1)$ . From $P(1,0)$ we get $f(-1)=-1$ , so $f(2k+1)=-1,\ \forall k\in \mathbb{Z}$ , whence $f\equiv -1$ .

If $f(0)=1$ , by $(*)$ and induction we get $f(2k)=2k+1,\ \forall k\in \mathbb{Z}$ . Also note $f(2k+1)=f(2k-1)+f(0)+1=f(2k-1)+2$ , so by induction $f(2k+1)=f(1)+2k\ (**)$
If $f(1)$ is odd, by $(**)$ , $f(f(1))=f(1)+2\cdot \dfrac{f(1)-1}{2}=2f(1)-1$ ; $f(f(1))=f(2)=3$ , so $f(1)=2$ , contradiction. If $f(1)$ is even, by $(*)$ , $f(f(1))=\dfrac{f(1)}{2}(f(0)+1)+f(0)=f(1)+1$ ; but $f(f(1))=f(2)=3$ , so $f(1)=2$ , whence $f(2k+1)=2k+2,\ \forall k\in \mathbb{Z}$ , so $f(x)=x+1,\ \forall x\in \mathbb{Z}$ .

Z K Y

The post below has been deleted. Click to close.

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

ABCDE

1963 posts

ABCDE

#8 h Jul 7, 2016, 8:35 PM • 4 Y

Y by chessgocube, centslordm, Adventure10, WiseTigerJ1

Let $A$ be the range of $f$ , and let $A+1=\{a+1\mid a\in A\}$ . The condition implies that for all $a,b\in A$ , $a-b-1,a+b+1\in A$ , so for all $m,n\in A+1$ , $m+n,m-n\in A+1$ . Hence, $A+1$ is the set of all integer multiples of some nonnegative integer $k$ .

If $k=0$ , then $A=\{-1\}$ , so $f(x)=-1$ . We can check that this works.

If $k>0$ , let $g(x)=\frac{f(x)+1}{k}$ . Since $A$ is the set of integers that are $-1\pmod{k}$ , $g$ is a surjective map from integers to integers. Substituting, we have that $g(x-kg(y)+1)=g(kg(x)-1)-g(y)$ . Since $g$ is surjective, we in fact have $g(x-kz+1)=g(kg(x)-1)-z$ , where $z=f(y)$ can be any integer. Setting $z=0$ , we have that $g(x+1)=g(kg(x)-1)$ .

Now, if $g(a)=g(b)$ for some $a\neq b$ , then $g(a+1)=g(b+1)=g(kg(a)-1)$ , so if $g$ is not injective then it is periodic for large inputs. But fixing $x$ , for some constants $c$ and $d$ we have that $g(c-kz)=d-z$ , so for sufficiently negative values of $z$ , and thus sufficiently large values of $c-kz$ , $g$ is unbounded, a contradiction. Hence, $g$ is injective, so we can conclude that $g(x+1)=g(kg(x)-1)\implies g(x)=\frac{x+2}{k}$ . Since $g$ maps integers to integers, $k=1$ , and we obtain a solution of $g(x)=x+2$ or $f(x)=x+1$ , which works.

Thus, our solutions are $f(x)=-1$ and $f(x)=x+1$ .

Z K Y

The post below has been deleted. Click to close.

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

Darn

996 posts

Darn

#9 h Jul 7, 2016, 9:07 PM • 43 Y

Y by SCP, doxuanlong15052000, PRO2000, Tommy2000, Kayak, Dukejukem, Fermat_Theorem, Myriam2003, ayan_mathematics_king, Bassiskicking, Lifefunction, Siddharth03, Imayormaynotknowcalculus, mathleticguyyy, Luchitha2, A-Thought-Of-God, mijail, microsoft_office_word, lneis1, Smkh, chessgocube, centslordm, Timmy456, Elnuramrv, myh2910, Bapun, Mathlover_1, megarnie, Chokechoke, hqxaev, Ibrahim_K, Adventure10, sabkx, D_S, jimmy_li, bin_sherlo, DrYouKnowWho, wizixez, EpicBird08, aidan0626, DroneChaudhary, Ismayil_Orucov, ZZzzyy

Here's an alternate solution.

The only solutions are $f(x)=\boxed{x+1}$ and $f(x)=\boxed{-1}$ .

Let $P(x,y)$ be the assertion that $f(x-f(y))=f(f(x))-f(y)-1.$ $P(x,f(x))$ implies that $f(x-f(f(x)))=-1,$ so $-1$ must be in the range of $f$ .

Let $f(a)=-1$ for some integral $a$ . Then from $P(x,a)$ we get $f(x+1)=f(f(x)). \quad (\star).$ Now from $P(f(x)-1,x)$ we find that $\begin{align*} f(-1)+1 &= f(f(f(x)-1)))-f(x) \\ &= f(f(x))-f(x) \\ &= f(x+1)-f(x), \end{align*}$ implying that $f(x+1)-f(x)$ is constant for all $x\in\mathbb{Z}$ . Since the domain of $f$ is $\mathbb{Z}$ , this means that $f(x)$ must be of the form $kx+c$ for some constants $k,c$ .

It remains to solve for $f$ . From $(\star)$ , we obtain $k(x+1)+c = k(kx+c)+c,$ so $k(x+1)=k(kx+c).$ If $k\not=0$ , then $kx+c=x+1,$ meaning that $f(x)=x+1$ . Otherwise, $f$ is constant, so from the hypothesis we get $c=c-c-1=-1,$ so $f(x)=-1$ .

Both of these functions satisfy the original condition, and so we have shown that $\boxed{-1\text{\;and\;}x+1}$ are indeed the only solutions to $f$ .

$\square$

Z K Y

The post below has been deleted. Click to close.

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

navi_09220114

487 posts

navi_09220114

#10 h Jul 8, 2016, 3:30 AM • 4 Y

Y by JoelBinu, centslordm, Adventure10, Mango247

The only solutions are $f(n)=-1$ for all $n\in \mathbb{Z}$ , and $f(n)=n+1$ for all $n\in \mathbb{Z}$ .

To verify that these are solutions, the first solution gives $-1=-1-(-1)-1$ , which is true. The second solution gives $x-(y+1)+1=(x+1)+1-(y+1)-1$ , which is also true. Now we will prove that these are the only soluitons.

To start, take $y=f(x)$ in $(1)$ , then we get $f(x-f(f(x)))=f(f(x))-f(f(x))-1=-1 \enspace{........ (2)}$ So by (2), choose $y=x-f(f(x))$ gives $f(y)=-1$ , so we have $f(x+1)=f(x-f(y))=f(f(x))-f(y)-1=f(f(x))$ Applying this successively we obtain $f(x+k)=f(f(x+k-1))=f(f(f(x+k-2)))=\cdots =f^{(k+1)}(x)\enspace\text{for all $x\in \mathbb{Z}, k\in\mathbb{N}$}\enspace{........ (3)}$ With this $(1)$ rewrites to $f(x-f(y))=f(x+1)-f(y)-1$
Now we claim that $f(-2)=-1$ . Take $x=f(y)$ , then using $(3)$ we get $f(0)=f(f(y)-f(y))=f(f(y)+1)-f(y)-1=f(f(f(y)))-f(y)-1=f(y+2)-f(y)-1$ so take $y=-2$ , $f(0)=f(0)-f(2)-1\Rightarrow f(-2)=-1$ .

So if we set $f(0)=a$ , then $f(y+2)-f(y)=a+1\enspace{........ (4)}$ Since $f(-2)=-1$ , by induction, $f(2m)=a+m(a+1)$ for all $m\in \mathbb{Z}$ . Likewise, if we set $f(1)=b$ , then $f(2m+1)=b+m(a+1)$ for all $m\in \mathbb{Z}$ . In particular, $f(2m+1)-f(2m)=b-a$ for all $m$ . Now we give a method to determine $b$ in terms of $f(4)$ .

Set $x=b+1, y=1$ , then $b=f(1)=f((b+1)-f(1))=f(b+2)-f(1)-1$ , but $f(b+2)=f(f(f(b)))=f(f(f(f(1))))=f(4)$ , so $b=f(4)-f(1)-1$ . So we have $b=\frac{f(4)-1}{2}\enspace{........ (5)}$ We split into $2$ cases.

Case 1: $a\neq-1$ .

In view of $(3)$ , if $a\neq -1$ , and if $f(p)=f(p+k)$ for some $p\in \mathbb{Z}, k\in \mathbb{N}$ , then for all $\ell\in \mathbb{N}$ , we obtain $f(p+\ell)=f^{(\ell+1)}(p)=f^{(\ell+1)}(p+k)=f(p+k+\ell)$ In particular, $f(p)=f(p+k)=f(p+2k)\Rightarrow k(a+1)=f(p+2k)-f(p)=0$ , clearly a contradiction. So $f$ is injective.

Take $x=y=2m$ , we get $f(2m-a-m(a+1))=f(2m-f(2m))=f(2m+1)-f(2m)-1=b-a-1$ , but if $a\neq 1$ , then $2m-a-m(a+1)$ takes more than $1$ value, which is impossible since $f$ is injective. So $a=1$ , and we get $f(2m)=2m+1$ for all $m\in \mathbb{Z}$ . Now, in view of $(5)$ , since $f(4)=5$ , $b=\frac{f(4)-1}{2}=2\Rightarrow f(2m+1)=2+m(a+1)=2m+2$ . So $f(n)=n+1$ for all $n\in \mathbb{Z}$ , which had been verified to be a solution.

Case 2: $a=-1$

Then $f(2m)=f(0)=-1$ , and $f(2m+1)=f(1)=b$ for all $m\in \mathbb{Z}$ . Then again in view of $(5)$ , we get $b=\frac{f(4)-1}{2}=-1$ , so $f(2m+1)=b=-1$ , so $f(n)=-1$ for all $n\in \mathbb{Z}$ , which is also verified to be a solution.

So the only solutions are $f(n)=-1$ for all $n\in \mathbb{Z}$ , and $f(n)=n+1$ for all $n\in \mathbb{Z}$ . Q.E.D

Z K Y

The post below has been deleted. Click to close.

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

adamov1

355 posts

adamov1

#11 h Jul 8, 2016, 4:22 AM • 6 Y

Y by Mobashereh, wheisenberg, centslordm, Adventure10, Mango247, H_Taken

Let $P(x,y)$ be the assertion. $P(x,f(x))$ gives that there exists $a$ such that $f(a)=-1$ . $P(x,a)$ gives
$f(x+1)=f(f(x))$ $P(f(x)-1,x)$ gives
$f(-1)=f(f(f(x)-1))-f(x)-1=f(f(x))-f(x)-1=f(x+1)-f(x)-1\longrightarrow f(x+1)-f(x)=f(-1)+1$ Thus $f$ is linear, so either $f$ is constant or injective. If $f$ is constant, it must clearly be identically $-1$ , which works, and if it is injective we have that $x+1=f(x)$ which also works.

This post has been edited 2 times. Last edited by adamov1, Jul 8, 2016, 4:22 AM

Z K Y

The post below has been deleted. Click to close.

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

gavrilos

233 posts

gavrilos

#12 h Jul 8, 2016, 12:54 PM • 2 Y

Y by Adventure10, Mango247

Hello.

This was also problem 3 in 2016 Greece Team Selection Test.

Z K Y

The post below has been deleted. Click to close.

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

rkm0959

1721 posts

rkm0959

#13 h Jul 9, 2016, 4:42 AM • 5 Y

Y by B.J.W.T, E.A.K, Pluto1708, Adventure10, Mango247

We show $f$ is linear.
$P(x,f(x))$ shows that there exists an $u$ such that $f(u)=-1$ .
$P(x,u)$ shows that $f(x+1)=f(f(x))$ . This gives us $f(x-f(y))=f(x+1)-f(y)-1$ .
Now $x=f(y)-1$ gives $f(-1)=f(f(y))-f(y)-1=f(y+1)-f(y)-1$ , so $f$ is linear as required.
Now set $f(x)=ax+b$ and solve. $a(x+1)+b=a(ax+b)+b$ , so $a=a^2$ and $a+b=ab+b$ .
This gives $a=1, b=1$ or $a=0$ . If $a=0$ , we easily see that $f(x) \equiv -1$ .
Therefore, the solution set is $f(x)=x+1$ and $f(x)=-1$ . $\blacksquare$

This post has been edited 1 time. Last edited by rkm0959, Jul 9, 2016, 4:42 AM

Z K Y

The post below has been deleted. Click to close.

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

DrMath

2130 posts

DrMath

#14 h Jul 9, 2016, 6:38 AM • 1 Y

Y by Adventure10

Let $P(x,y)$ denote the given assertion.

By $P(x, f(x))$ we have $f(x-f(f(x)))=-1$ . Thus there is a value $y$ such that $f(y)=-1$ . Taking $P(x,y)$ with $f(y)=-1$ gives $f(x+1)=f(f(x))$ .

Suppose $f$ is one to one. Then we instantly get that $f(x)=x+1$ .

Else, suppose $f(a)=f(b)$ for $a, b$ distinct. We claim this gives $f(x)=-1$ for all $x$ . Note $P(a,y)$ and $P(b,y)$ gives $f$ is periodic. Let the period be $p$ , and suppose for the sake of contradiction we can take $y$ to be a value such that $f(y)\neq -1$ . Then $P(x-1, y)$ gives $f(x-1-f(y))=f(x)-f(y)-1$ . Thus, if $r$ is in the range of $f$ , so is $r-f(y)-1$ . Thus, for some integer $k$ , $r$ and $r-kp$ are both in the range of $f$ . But take $f(y)=r$ and $f(y')=r -kp$ . $P(x,y)$ and $P(x, y')$ gives our contradiction, as $f$ has period $p$ . Thus if $f$ is periodic then $f(x)=-1$ for all $x$ .

This post has been edited 1 time. Last edited by DrMath, Jul 9, 2016, 6:38 AM

Z K Y

The post below has been deleted. Click to close.

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

mathmoGJ

47 posts

mathmoGJ

#15 h Jul 10, 2016, 9:04 PM • 2 Y

Y by Adventure10, Mango247

Was also Problem 2 on the UK Team selection test 2.

Z K Y

The post below has been deleted. Click to close.

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

hnkevin42

226 posts

hnkevin42

#16 h Jul 11, 2016, 10:38 AM • 1 Y

Y by Adventure10

This will be long.

We have the following basic pieces of information.

Setting $(x, y) \rightarrow (f(0), 0)$ yields $f(f(f(0))) = 2f(0) + 1. \quad (\textbf{I})$
Setting $(x, y) \rightarrow (0, f(0))$ yields $f(-f(f(0))) = -1. \quad (\textbf{II})$
Via $\textbf{(II)}$ , setting $(x, y) \rightarrow (x, -f(f(0)))$ yields $f(x + 1) = f(f(x)). \quad (\textbf{III})$

We then attack with the following lemmas.

Lemma 1: For every integer $n$ , we have $f(n(f(0) + 1)) = (n + 1)f(0) + n$ .
Proof: We induct both ways, starting with the obviously true base case of $n = 0$ and going in the negative and positive direction.
We go in the positive direction. If $n$ is not negative, setting $(x, y) \rightarrow ((n + 1)f(0) + n, n(f(0) + 1))$ yields, using $\textbf{(III)}$ ,
$f(0) = f(f((n + 1)f(0) + n)) - (n + 1)f(0) - n - 1$ $\implies f((n + 1)f(0) + (n + 1)) = f((n + 1)(f(0) + 1)) = (n + 2)f(0) + (n + 1)$ which completes the inductive step. In the negative direction, setting $(x, y) \rightarrow (n(f(0) + 1) - 1, 0)$ yields, again using $\textbf{(III)}$ ,
$f((n - 1)f(0) + (n - 1)) = f(f(n(f(0) + 1) - 1)) - f(0) - 1$ $\implies f((n - 1)(f(0) + 1)) = (n + 1)f(0) + n - f(0) - 1 = nf(0) + (n - 1)$ which completes the inductive step, proving Lemma 1.

Lemma 2: We either have $f(0) = 1$ or $f(0) = -1$ .
Proof: Note that by $(\textbf{III})$ , we have $f(f(0)) = f(1)$ . Since $f(f(x)) = f(x + 1)$ for all integers $x$ , we have that $f$ is periodic, for all $x \ge \min(f(0), 1)$ if $f(0) \ne 1$ . For these $x$ , $f$ is bounded. But from Lemma 1, $f$ must be unbounded for positive $x$ and for $f(0) \ne -1$ . This is because, if $f(0)$ is nonnegative, both $n(f(0) + 1)$ and $f(n(f(0) + 1))$ are positive and strictly increasing as $n$ grows in the positive integers. Likewise, if $f(0) < -1$ , both $n(f(0) + 1)$ and $f(n(f(0) + 1))$ are positive and strictly increasing as $n$ gets more negative, so either way, $f$ is unbounded in the positive integers if $f(0) \ne -1$ . Since $f$ is periodic and unbounded in the positive integers for all $f(0)$ not equal to $1$ or $-1$ , we cannot have $f(0)$ be any other value than $1$ or $-1$ .

END LEMMA: The solutions, and the only solutions, are $f(x) = x + 1$ and $f(x) = -1$ .
Proof: Setting $(x, y) \rightarrow (0, 0)$ yields $(\star) f(-f(0)) = f(f(0)) - f(0) - 1 = f(1) - f(0) - 1$ via $\textbf{(III)}$ . Then setting $(x, y) \rightarrow (f(1) - 1, -f(0))$ yields via $\textbf{(III)}$ , $f(f(0)) = f(f(f(1) - 1)) - f(1) + f(0) \implies f(f(1)) = 2f(1) - f(0).$ We know $f(f(1)) = f(f(f(0))) = 2f(0) + 1$ from $\textbf{(I)}$ and $\textbf{(III)}$ , so then $2f(1) = 3f(0) + 1$ .

If $f(0) = 1$ , then $f(1) = 2$ and, with $(\star)$ , $f(-1) = 0$ . Then, plugging in $(x, y) \rightarrow (x, -1)$ yields that for all integers $x$ , we need $f(x) = f(f(x)) - 1 \implies f(x + 1) = f(x) + 1$ . From here we get that $f(0) = 1$ leads to the one solution $f(x) = x + 1$ .

If $f(0) = -1$ , then $f(1) = -1$ and, with $(\star)$ , $f(2) = -1$ . Then, plugging in $(x, y) \rightarrow (x, -1)$ yields that for all integers $x$ , we need $f(x + 1) = f(f(x))$ . A quick induction starting with $x = 1$ yields that for all positive integers $x$ , $f(x) = -1$ . Now suppose $f(k) = a \ne -1$ for any $k < -1$ . Setting $(x, y) \rightarrow (x, -1)$ yields that for all integers $x$ , we need $f(x - a) = f(x + 1) - a - 1$ . If we choose a positive integer $x = k > |a|$ , then we have $k - a, k + 1$ are positive integers and $f(k - a) = f(k + 1) - a + 1 \implies -1 = -1 - a + 1$ , which is a contradiction since we said $a \ne 1$ . Thus, we have the one solution $f(x) = -1$ for all $x$ .

Since both solutions easily work when plugged back into the original equation, The answer is $\boxed{f(x) = x + 1, f(x) = -1.}$

This post has been edited 2 times. Last edited by hnkevin42, Jul 12, 2016, 12:49 PM
Reason: Copy error

Z K Y

The post below has been deleted. Click to close.

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

tenplusten

1000 posts

tenplusten

#17 h Oct 17, 2016, 2:49 PM • 2 Y

Y by Adventure10, Mango247

Good problem.

Claim 1: There exist $a\in R$ such that $f(a)=-1$ .
Proof:Just see $P(x,f(x))$

Claim 2: $f(f(x))=f(x+1)$
Proof: $P(x,a)$ $\implies$ $f(x+1)=f(f(x))$

Claim 3: $f(f(f(x)))-f(x)=f(0)+1$
Proof: Just see $P(f(x),x)$

Claim 4: $f(x+2)=f(x)+f(0)+1$
Proof: Using "Claim 2" we get $f(f(f(x)))=f(f(x+1))=f(x+2)$
So $f(f(f(x)))-f(x)=f(0)+1=f(x+2)-f(x)$ .

Since we got $f(x+2)=f(x)+f(0)+1$
Easy to show that $f(x)=x+1$ and $f\equiv-1$
So solutions are $f(x)=x+1$ for all $x\in Z$ and $f\equiv -1$

This post has been edited 6 times. Last edited by tenplusten, Feb 6, 2017, 3:42 PM

Z K Y

The post below has been deleted. Click to close.

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

MSTang

6012 posts

MSTang

#18 h Feb 3, 2017, 6:06 AM • 3 Y

Y by adityaguharoy, Adventure10, Mango247

Claim 1: $-1$ is in the range of $f$ .

Proof: Taking $y=f(x)$ gives $f(x-f(f(x)) = -1$ for all $x$ . $\spadesuit$

Claim 2: Over all $x$ , the quantity $f(f(x)) - f(x)$ is constant.

Proof. Let $a, b$ be integers. Taking $x=f(a)+f(b)$ and $y=a$ gives $f(f(b)) = f(f(f(a)+f(b))) - f(a) - 1.$ Taking $x=f(a)+f(b)$ and $y=b$ gives $f(f(a)) = f(f(f(a)+f(b))) - f(b) - 1.$ Comparing the two equations gives $f(f(a)) - f(a) = f(f(b)) - f(b)$ , as claimed. $\spadesuit$

Finisher. Let $f(f(x)) - f(x) = k$ for some constant $k$ . Then the given equation becomes $f(x-f(y)) = f(x) - f(y) + (k-1)$ for all $x, y$ . Using Claim 1, choose $y$ in the above equation such that $f(y) = -1$ , giving $f(x+1) = f(x) + k$ for all $x$ . Since $f$ has domain $\mathbb{Z}$ , we conclude that $f$ is of the form $f(x) = kx + c$ for some constants $k$ and $c$ . In the original equation, we need $k(x-ky-c)+c = k(kx+c) + c - ky - c - 1$ or $kx - k^2y - ck + c = k^2x + ck - ky - 1.$ Comparing $x$ coefficients gives $k = k^2$ , so $k \in \{0, 1\}$ . If $k=0$ , then $c = -1$ , giving the solution $f(x) = -1$ for all $x$ . If $k=1$ , then $c = 1$ , giving the solution $f(x) = x + 1$ for all $x$ . It is easy to check that both these functions work. $\square$

Z K Y

The post below has been deleted. Click to close.

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

adityaguharoy

4657 posts

adityaguharoy

#19 h Feb 3, 2017, 6:09 AM • 2 Y

Y by Adventure10, Mango247

MSTang wrote:

Claim 1: $-1$ is in the range of $f$ .

Proof: Taking $y=f(x)$ gives $f(x-f(f(x)) = -1$ for all $x$ . $\spadesuit$

Claim 2: Over all $x$ , the quantity $f(f(x)) - f(x)$ is constant.

Proof. Let $a, b$ be integers. Taking $x=f(a)+f(b)$ and $y=a$ gives $f(f(b)) = f(f(f(a)+f(b))) - f(a) - 1.$ Taking $x=f(a)+f(b)$ and $y=b$ gives $f(f(a)) = f(f(f(a)+f(b))) - f(b) - 1.$ Comparing the two equations gives $f(f(a)) - f(a) = f(f(b)) - f(b)$ , as claimed. $\spadesuit$

Finisher. Let $f(f(x)) - f(x) = k$ for some constant $k$ . Then the given equation becomes $f(x-f(y)) = f(x) - f(y) + (k-1)$ for all $x, y$ . Using Claim 1, choose $y$ in the above equation such that $f(y) = -1$ , giving $f(x+1) = f(x) + k$ for all $x$ . Since $f$ has domain $\mathbb{Z}$ , we conclude that $f$ is of the form $f(x) = kx + c$ for some constants $k$ and $c$ . In the original equation, we need $k(x-ky-c)+c = k(kx+c) + c - ky - c - 1$ or $kx - k^2y - ck + c = k^2x + ck - ky - 1.$ Comparing $x$ coefficients gives $k = k^2$ , so $k \in \{0, 1\}$ . If $k=0$ , then $c = -1$ , giving the solution $f(x) = -1$ for all $x$ . If $k=1$ , then $c = 1$ , giving the solution $f(x) = x + 1$ for all $x$ . It is easy to check that both these functions work. $\square$

It is somewhat similar to the solution I had for this problem.

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

674 posts

Ilikeminecraft

#164 h Jan 24, 2025, 11:08 PM

Y by

The answer is $f\equiv-1, f\equiv x + 1,$ both of which clearly work.
let $P(x, y)$ be the assertion.
$P(x, f(x))\implies f(x - f(f(x))) = f(f(x)) - f(f(x)) -1 = -1.$
$P(x, x - f(f(x)))\implies f(x + 1) = f(x - f(x - f(f(x)))) = f(f(x)) - f(x - f(f(x))) - 1 = f(f(x)).$
$P(x, y), P(x - 1, y)\implies$
$\begin{align*} f(x - f(y)) & = f(x + 1) - 1 - f(y) \\ f(x - 1 - f(y)) & = f(x) - 1 - f(y) \end{align*}$ By subtracting, we get $f(x - f(y)) - f(x - 1 - f(y)) = f(x + 1) - f(x).$ Taking $x= f(y)$ , we get $f(0) - f(-1) = f(f(y) + 1) - f(f(y)) = f(f(f(y))) - f(f(f(y - 1))).$ Hence, $f(f(f(x)))$ is a linear function since its finite difference is constant. We write $f(f(f(x))) = ax + b.$
$P(f(y), y)\implies f(0) = f(f(f(y))) - f(y) - 1\implies f(y) = ay + b + 1 - f(0),$ or $f$ is linear.

let $f(x) = ax + b.$ plug this in to get $ax - a^2y - ab + b = a^2x + ab + b - ay - b - 1.$ Thus, $a = 1, 0.$ If $a = 1, b = 1,$ and if $a = 0, b = -1.$

This post has been edited 1 time. Last edited by Ilikeminecraft, Jan 24, 2025, 11:13 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

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

EpicBird08

1756 posts

EpicBird08

#165 h Jan 28, 2025, 4:31 PM

Y by

The only solutions are $f(x) = -1$ and $f(x) = x + 1$ , which both work. Now we show that these are all the solutions. Let $P(x,y)$ denote the given assertion.

$P(0,f(0))$ gives $f(-f(f(0))) = -1.$ Letting $u = -f(f(0)),$ we see that $P(x,u)$ gives $\boxed{f(f(x)) = f(x+1)}.$ Then $P(f(x),x)$ gives $f(0) = f(f(f(x))) - f(x) - 1 = f(f(x+1)) - f(x) - 1 = f(x+2) - f(x) - 1.$ This implies that $\boxed{f(x+2) = f(x) + f(0) + 1}.$ We now consider two cases.

Case 1: $f(0) = -1.$ The above boxed equation immediately gives $f(2k) = -1$ for all $k \in \mathbb{Z}.$ Let $f(1) = f(2k+1) = c$ for integers $k.$
Subcase 1: $c$ is odd. Then $P(2k,2k-1)$ gives $c = c - c - 1 \implies c = -1,$ yielding our first solution $f(x) = -1$ for all $x.$
Subcase 2: $c$ is even. Then $P(2k+1,2k+1)$ gives $c = -1 - c - 1 \implies c = -1,$ a contradiction.
Thus this case has been exhausted, and it yields one solution $\boxed{f(x) = -1}.$

Case 2: $f(0) \ne -1.$ Then the first boxed equation implies that if $f(x) \equiv x+1 \pmod{2},$ then $f(x) = x+1.$ By the second boxed equation, we know $f(2) = 2 f(0) + 1$ is odd, as is $2 + 1 = 3.$ Hence $f(2) = 3,$ immediately giving $f(0) = 1.$ Hence $f(x) = x+1$ for even $x.$ Let $f(x) = x + c$ for odd $x.$ Again, the first boxed equation implies $f(1+c) = f(f(1)) = f(2) = 3.$ Hence either $1+c+1 = 3$ or $1 + 2c = 3.$ Both cases give $c = 1,$ yielding our second solution $\boxed{f(x) = x + 1}$ for all $x.$

Hence the only solutions are those claimed at the beginning.

This post has been edited 2 times. Last edited by EpicBird08, Jan 29, 2025, 12:11 AM

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

674 posts

Ilikeminecraft

#166 h Feb 3, 2025, 7:03 AM

Y by

The solution is $f\equiv 1, x + 1.$

Take $y = f(x)$ to get that there exists $a = x - f(f(x))$ such that $f(a) = -1.$

Take $y = a$ to get that $f(x + 1) = f(f(x)).$

If $f$ is injective, we are done, as this implies $x + 1 = f(x),$ which indeed works.

Now, assume $f$ is not injective, and $f(a) = f(b)$ for some $a\neq b.$ Note that we can get $f(a + 1) = f(f(a)) = f(f(b)) = f(b + 1),$ and so thus, $f(x) = f(x + k(a - b))$ for some $k \in \mathbb Z.$

Take $x = f(y)$ to get $f(0) = f(f(f(y))) - f(y) - 1 = f(y + 2) - f(y) - 1$ to get that $f(2k)$ is linear and $f(2k + 1)$ is linear. By $f(x) = f(x + k(a - b)),$ we can also get that $f(2k) = c_2, f(2k + 1) = c_1$ for two constants(not necessarily the same). Finally, we do parity casework on $c_1, c_2:$
\begin{enumerate}
\item If $c_2\equiv 0\pmod 2,$ then taking $x\equiv y\equiv 0\pmod 2$ tells us $c_2 = -1,$ contradiction.
\item If $c_1 \equiv 0\pmod 2,$ then taking $x\equiv 0, y\equiv 1\pmod 2$ tells us $c_1 = -1,$ contradiction.
\item If $c_1 \equiv c_2 \equiv 1 \pmod 2,$ taking $x\equiv 0\pmod 2$ tells us $f(y) = -1,$ which finishes.
\end{enumerate}

Z K Y

The post below has been deleted. Click to close.

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

Bardia7003

22 posts

Bardia7003

#167 h Feb 22, 2025, 4:40 PM

Y by

Let $P(x,y)$ denote the given assertion.
$\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} P(f(x),x): f(0) = \underline{f(f(f(x))) - f(x) - 1 \quad (\RomanNumeral{1})} \\ P(x, f(x)): \underline{f(x - f(f(x))) = -1 \quad (\RomanNumeral{2})} \\ P(x, x - f(f(x))): f(x - f(x - f(f(x)))) = f(f(x)) - f(x - f(f(x))) - 1 \xrightarrow{\RomanNumeral{2}} \underline{f(x+1) = f(f(x)) \quad (\RomanNumeral{3})}$
So by $\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} (\RomanNumeral{3})$ we have that $f(f(f(x))) = f(f(x+1)) = f(x+2)$ , and putting that in $\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} (\RomanNumeral{1})$ we have: $\underline{f(0) + 1 = f(x+2) - f(x) \newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} \quad (\RomanNumeral{4})}$ . Which means $f(2x)$ is linear. So $f(2x) = ax + b$ , which $a = f(0) + 1 = b + 1$ , So $f(2x) = (b+1)x + b$ .
$f(2x+1)$ is also linear, so $f(2x + 1) = ax + c (a = f(0) + 1)$
We want to prove that $b$ is odd, so we assume otherwise. For an odd $x$ , $f(f(2x)) = f((b+1)x + b)$ , $(b+1)x$ is odd and $b$ is even so the value is odd: $f(f(2x)) = (b+1)(\frac{(b+1)x + b - 1}{2}) + c$ . Also by $\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} (\RomanNumeral{3})$ we know $f(f(2x)) = f(2x + 1) = (b+1)x + c$
So $(b+1)x = (b+1)(\frac{(b+1)x + b - 1}{2})$ . $b$ is even so $b+1\neq0$ and we can cross it out: $x = \frac{bx + x + b - 1}{2} \rightarrow x = bx + b -1 \rightarrow (1-b)x = (b - 1) \xrightarrow{b-1\neq0} x = -1$ , but we had the equation for any odd $x$ , hence contradiction. As a result, we proved $b$ is odd.
Now we know $f(2x+1) = ax+c \xrightarrow{\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} \RomanNumeral{3}} f(f(2x)) = ax + c \rightarrow f(ax + b) = ax + c \xrightarrow{x := 0} f(b) = c$
As we know $b$ is odd, so:
$c = f(b) = a(\frac{b-1}{2}) + c \rightarrow a(\frac{b-1}{2}) = 0$ so $b = 1$ or $a = 0$ .
Case 1: $a = 0$ . Then $b+1 = 0, f(2x) = b \rightarrow f(2x) = -1$ and $f(2x + 1) = c$ . If c is odd, then by $\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} (\RomanNumeral{3})$ we know $f(c+1) = f(f(c)) = f(c) = c$ and $c + 1$ is even so $-1 = c = f(2x+1)$ .
Hence $\boxed{f(x) = -1 \quad \forall x \in \mathbb{Z}}$ is the solution in this case, which indeed works.
Case 2: $b=1$ . Then $f(2x) = 2x + 1, f(2x + 1) = 2x + c$ . By $\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} (\RomanNumeral{2})$ we know $\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} f(2x - f(f(2x)) = -1 \xrightarrow{\RomanNumeral{3}} f(2x - f(2x + 1)) = -1 \rightarrow f(2x - 2x - c) = -1 \rightarrow f(-c) = -1$ . If c is even then $-c +1 = -1 \rightarrow c = 2$ , and we want to prove $c$ is even so we can conclude $c=2$ , so we assume not. If c is odd then $f(f(c)) = f((c-1) + c) = ((2c-1)-1) + c$ , and by $\newcommand{\RomanNumeral}[1]{\MakeUppercase{\romannumeral #1}} (\RomanNumeral{3})$ we know that $f(f(c)) = f(c+1) = (c+1) + 1$ so $3c - 2 = c + 2 \rightarrow c = 2$ but we supposed c is odd, contradiction.
So we proved $c$ is even and as a result $c=2$ , as we proved. Now we have that $f(2x) = 2x+1, f(2x+1) = 2x+2$ , so we can generally conclude $\boxed{f(x) = x+1 \quad \forall x \in \mathbb{Z}}$ in this case, which is also a solution.
So both cases are solved and we found all the solutions. $\blacksquare$
Please feel free to point out if I've made any mistakes through this proof, thanks.

Z K Y

The post below has been deleted. Click to close.

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

Ihatecombin

69 posts

Ihatecombin

#168 h Mar 13, 2025, 1:27 PM

Y by

A pretty unique problem, bit annoying to be honest lol. The only solutions are $f(x) \equiv -1$ and $f(x) \equiv x+1$ .
You can use $P(x,f(x))$ to get
$f(x - f^2(x)) = -1$ Afterwards let $f(r) = -1$ , we can use $P(x,r)$
to get
$f(x+1) = f^2(x)$ Notice that the equation can be transformed into
$f(x-f(y)) = f(x+1) - f(y) - 1$ Let $f(p+1) = k \neq -1$ (otherwise $f(x) \equiv -1$ , which works).
Notice that if we use $P(k+p+1,p+1)$ , then we must have
$f(p+1) = f(k+p+2) -k-1 \Longrightarrow 2k+1 = f(k+p+2)$ Since $k \neq -1$ , we must have that $2k+1 \neq k$ and $2k+1$ is also in the image of $f(x)$ ,
thus $2(2k+1) + 1$ is also in the image and so on. Therefore the set containing all the integers which are in the image of $f(x)$ is infinite.
Now let $n$ be a number such that $f(n) = k \neq -1$ for some $k$ . Substituting $P(x,n)$ we have
$f(x-k) = f(x+1)-k-1$ we already know that if $k$ is in the image of $f(x)$ , then $2k+1$ is in the image. Let $f(m) = 2k+1$ , we can substitute $P(x,m)$ to get
$f(x-2k-1) = f(x+1) - 2k - 2$ Thus we must have
$f(x-2k-1) + k + 1= f(x-k) \Longrightarrow f(x) = f(x-k-1) +k+1$ for some $k \neq -1$ .

Notice that since $f(x+1) = f^2(x)$ , if $f(x)$ is injective then we are done $f(x) \equiv x+1$ .
Therefore assume $f(x) \not\equiv -1$ and $f(x) \not\equiv x+1$ and $f(x)$ is not injective. Let $f(a) = f(b)$ , notice that since $f(x+1) = f^2(x)$ , we must have
$f(a+1) = f^2(a) = f^2(b) = f(b+1)$ similarly
$f(a+2) = f^2(a+1) = f^2(b+1) = f(b+2) \Longrightarrow f(a) = f(b) = f(2b-a)$ By induction we have
$f(a) = f(xb-(x-1)a)$ However substituting $k+1$ , we have
$f(a) = f([k+1](b-a) + a)$ But since $f(x) = f(x-k-1) + k +1$ , we easily get
$f(a) = f([k+1](b-a) + a) = f(a) + (k+1)(b-a)$ This is a clear contradiction.

This post has been edited 1 time. Last edited by Ihatecombin, Mar 13, 2025, 1:28 PM
Reason: Apparently \textbf{} doesn't cause bold text in AOPS

Z K Y

The post below has been deleted. Click to close.

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

Adywastaken

74 posts

Adywastaken

#169 h Apr 21, 2025, 11:42 AM

Y by

$y=f(x)\implies f(x-f(f(x)))=-1$
$y=x-f(f(x))\implies f(x+1)=f(f(x))$
$x=f(y)-1\implies f(-1)+1=f(f(f(x)-1))-f(x)=f(f(x))-f(x)=f(x+1)-f(x)$
So, $f=mx+c$ , and matching coefficients,
$m^2=m, 2mc=c+1$
So, $(m,c)=(0,-1),(1,0)$
$f(x) \equiv -1$ or $f(x)=x+1$

Z K Y

The post below has been deleted. Click to close.

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

Jakjjdm

4 posts

Jakjjdm

#170 h Apr 22, 2025, 11:52 PM

Y by

The only solutions are $f(x) \equiv -1$ and $f(x) = x + 1$ . Let $P(m,n)$ be the main equation plugging $x = m$ and $y = n$ . $P(x,f(x)) : f(x - f(f(x))) = - 1$ , so let k be an integer such that $f(k) = -1$ , so $P(x,k) : f(x +1) = f(f(x))$ . $P(f(y) - 1, y) : f(-1) + 1 = f(f(f(y) - 1)) - f(y) = f(y + 1) - f(y)$ , so the function is linear. Now, Just check the cases when $f(x) \equiv c$ , giving $f(x) \equiv -1$ , and check when $f(x) = x + c$ , that gives $f(x) = x + 1$ , and we're done.

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1310 posts

ezpotd

#171 h May 11, 2025, 1:49 AM

Y by

We claim the only such functions that work are $f(x) = x + 1$ and $f(x) = -1$ . It is obvious to see that both of these work.

Set $y = f(x)$ , then $f$ is $-1$ at some input, then set $y$ such that $f(y) = -1$ , so $f(x + 1) = f(f(x))$ . If $f$ is injective, we are done. Otherwise, take two inputs $a,b$ such that $f(a) = f(b), a \neq b$ . Then we also have $f(a +1) = f(f(a)) = f(f(b)) = f(b + 1)$ , applying this inductively gives $f$ periodic with period $b -a$ . Assume $f$ is periodic, thus it has finite range. Now consider the range $R$ of $f$ , take the largest element $l$ in $R$ and the smallest element $s$ in $R$ , then since $f(f(x)) = f(x + 1)$ , $f(f(x))$ has the same range $R$ , so set $x$ with $f(f(x)) = l, y$ with $f(y) = s$ , then we have $l - s - 1 \in R$ . We must then have $s \ge -1$ otherwise a number at least $l + 1$ would be in $R$ , contradiction, but since $-1 \in R$ we have $s = -1$ . Likewise $l = -1$ , so $f$ must be constantly $-1$ .

Z K Y

The post below has been deleted. Click to close.

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

youochange

180 posts

youochange

#172 h May 13, 2025, 8:53 AM

Y by

ABCDE wrote:

Determine all functions $f:\mathbb{Z}\rightarrow\mathbb{Z}$ with the property that $f(x-f(y))=f(f(x))-f(y)-1$ holds for all $x,y\in\mathbb{Z}$ .

can someone pls veify my sol :maybe:

f(x)=x+1

This post has been edited 2 times. Last edited by youochange, May 13, 2025, 12:31 PM

Z K Y

The post below has been deleted. Click to close.

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

youochange

180 posts

youochange

#173 h May 15, 2025, 3:08 AM

Y by

Bummmmmp

Z K Y

The post below has been deleted. Click to close.

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

pco

23515 posts

pco

#174 h May 15, 2025, 3:27 AM • 1 Y

Y by youochange

youochange wrote:

ABCDE wrote:

Determine all functions $f:\mathbb{Z}\rightarrow\mathbb{Z}$ with the property that $f(x-f(y))=f(f(x))-f(y)-1$ holds for all $x,y\in\mathbb{Z}$ .

can someone pls veify my sol :maybe:

Let $P(x,y)$ be the assertion.

Let $f(a)=0$ for a special $a \in \mathbb Z$
...

And what if such $a$ does not exist ?
(which is the case in the forgotten - in your post - solution $f\equiv -1$ )

Z K Y

The post below has been deleted. Click to close.

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

heheman

1007 posts

heheman

#175 h May 21, 2025, 8:59 PM

Y by

BRO MY COMPUTER JUST RESTARTED AND DELETED ALL MY PROGRESS

Z K Y

The post below has been deleted. Click to close.

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

heheman

1007 posts

heheman

#176 h May 21, 2025, 9:00 PM

Y by

Answers are $f(x) = -1$ for all $x$ or $f(x) = x+1$ for all $x$ .

Put $y=f(x)$ to see some $f(u) = -1$ .
Put $(x, u)$ to see that $f(f(x)) = f(x+1)$ .
If $f$ is injective, then $f(x) = x+1$ . Otherwise, some $f(a)=f(b)$ with $a \ne b$ .
Then $f(f(a)) = f(f(b))$ implies that $f(a+1) = f(b+1)$ etc. so $f$ is periodic.
Suppose $g$ and $l$ are the greatest and least values in the period. Let $x_g$ and $x_l$ be very large values of $x$ that achieves $g, l$ when plugging them into $f$ (we want $x_g, x_l$ to be large so $x-f(y)$ stays in the periodic part). Note that $(x_l-1, x_g)$ and $(x_g-1, x_l$ gives $l-g-1$ and $g-l-1$ are both in the period. If $l < -1$ the second expression is larger than $g$ , contradiction. If $g > -1$ , it would make the first expression less than $l$ , contradiction. Then we have $-1 \le l \le g \le -1$ , so $l = g = -1$ . So $f(x) = -1$ .

Z K Y

The post below has been deleted. Click to close.

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

heheman

1007 posts

heheman

#177 h May 21, 2025, 9:01 PM

Y by

comment

This post has been edited 1 time. Last edited by heheman, May 21, 2025, 9:02 PM

Z K Y

The post below has been deleted. Click to close.