Find all functions $f$ such that $f(x-f(y)) = f(f(x)) - f(y) - 1$ Find all functions $f : \mathbb{Z} \to \mathbb{Z}$ such that $f(x-f(y)) = f(f(x)) - f(y) - 1$. 
So far, I've managed to prove that if $f$ is linear, then either $f(x) = x + 1$ or $f(x) = -1$ must be true. I did this by plugging in $x=0$ to the above equation, which yields
$$ f(-f(y)) = f(f(0)) - f(y) - 1$$
and plugging in $x$ instead of $y$ and subtracting, this becomes
$$ f(-f(y)) - f(-f(x)) = f(x) - f(y)$$
Assuming $f(x) = ax + b$ then gives
\begin{align*}
f(-ay-b) - f(-ax-b) = ax - ay &\Rightarrow -a^2y - ab + a^2x + ab = a(x-y) \\&\Rightarrow a^2(x-y) = a(x-y) .
\end{align*}
Thus $a=1$ or $a=0$. If $a=0$, then the original equation becomes $b = b - b - 1$, thus $b=-1$. If $a=1$, the original equation becomes
$$ x-y-b+b = x+2b-y-b-1 \Longrightarrow b=1.$$
I briefly tried finding a quadratic function that works but didn't find anything. So my question is: how can I either show that $f$ must be linear or find all other representations?
 A: Let $f\colon \Bbb Z\to \Bbb Z$ be a any function function with $$\tag0f(x-f(y)) = f(f(x)) - f(y) - 1$$
for all $x,y\in\Bbb Z$.
Letting $y=f(x)$ we find $$f(x-f(f(x)))=-1. $$
So for $a=-f(f(0))$ we have $f(a)=-1$. Then with $y=a$, $$\tag1f(x+1)=f(f(x)) $$
Then $(0)$ becomes
$$\tag2 f(x-f(y))=f(x+1)-f(y)-1 $$
Or with $g(x):=f(x)+1$ (and $x\leftarrow x-1$)
$$\tag3g(x-g(y))=g(x)-g(y)$$
From $(3)$ we see that the image of $g$ is a subgroup of $\Bbb Z$, hence it is either $\{0\}$ (in which case $f(x)=-1$), or $c\Bbb Z$ for some $c\ge 1$.
In that case,  for $n\in\Bbb Z$ we find $y$ with $g(y)=nc$ and so have $g(x+ nc)=g(x)+nc$. Thus  $g$ is determined by the values $g(0),\ldots, g(c-1)$. On the other hand, these values can indeed be chosen freely. In other words:
Claim 1. Let $c\in\Bbb N$ and $b_0,\ldots, b_{c-1}\in\Bbb Z$. Then the function $g$ given by 
$$ g(x)= (n+b_r)c$$
where $x=nc+r$, $0\le r<c$
is a solution to $(3)$, and all non-zero solutions of $(3)$ are obtained this way.
Proof.
Let $x=nc+r$, $y=mc+s$ with $0\le r,s<c$. Then 
$$\begin{align}g(x-g(y))&=g(nc+r-(m+b_s)c)\\
&=g((n-m-b_s)c+r)\\
&=(n-m-b_s+b_{r})c\\
&=(n+b_r)c-(m+b_s)c\\&=g(x)-g(y)\end{align}$$
That all non-zero solutions are of this form has been shown above. $\square$
Then the solutions $f$ of $(2)$  (apart from $f(x)=-1$) are precisely those of the form $f(x)=g(x)-1$ with $g$ as in Claim 1.
Such $f$ is a solution to the original $(0)$ if and only if we additionally have $(1)$ for all $x$.
Note that for $x=nc+r$, $0\le r<c$, we have $f(x)=g(x)-1=(n+b_r)c-1=(n+b_r-1)c+c-1$ so that $$f(f(x))=(n+b_r-1+b_{c-1})c-1.$$ 
On the other hand, 
$$f(x+1)=g(x+1)-1=\begin{cases}(n+b_{r+1})c-1&\text{if }r<c-1\\(n+1+b_0)c-1&\text{if }r=c-1\end{cases}$$
We conclude that $b_{r+1}=b_r+b_{c-1}-1$ for $0\le r<c-1$, and that $2b_{c-1}-1=b_0+1$. From the first we see that $b_r=b_0+rb_{c-1}-r$, so 
$$\begin{align}b_{c-1}&=b_0+1+(c-1)b_{c-1}-c\\
&=2b_{c-1}-1+(c-1)b_{c-1}-c\\
&=(c+1)b_{c-1}-c-1\end{align}$$ and finally
$$b_{c-1} = \frac {c+1}c.$$
This is an integer only for $c=1$ and in that case we arrive at $b_0=2$
Thus the only solutions to $(0)$ apart from $f(x)=-1$ is
$$f(x)=x+1.$$
A: if we can say that $f$ is polynomial, then since $f(-f(y))-f(-f(x))=f(x)-f(y)$, we can say that $f(-f(y))+f(y)=f(-f(x))+f(x)$ for any $x,y \in Z$. Hence, $f(-f(x))+f(x)$ is constant for all $x \in Z$. 
If $deg(f) >0$ then $f$ has infinitely many values, so we can say $f(-x)+x$ is constant, say $f(-x)+x=c$.
Then $f(-x)=c-x$, or $f(x)=c+x$
If $deg(f)=0$ then $f$ is constant and you know the answer.
A: If the functions attains $0$ at some point, it is linear and $f(n)=n+1$.
Suppose $f(y)=0$, for some $y \in \mathbb{Z}$ then we find for $x \in \mathbb{Z}$
$$f(x)=f(x-f(y))=f(f(x))-f(y)-1 = f(f(x))-1$$
So in particular $x=y$ gives $f(0)= 1$.
Now, if $f(n)=n+1$, then $x=n$ gives $$n+1 = f(n) =f(f(n))-1= f(n+1)-1$$
So $f(n+1) = n+2$, thus for $n \in \mathbb{N}$ we have $f(n) = n+1$.
For the other way, let $x=0$ and $y=n-1$ then
$$f(-n) = f(x - f(n-1)) = f(f(x)) -f(n-1) -1 =f(1) - n-1 =-n+1$$
So we see that if $f(y) =0$ for some $y \in \mathbb{Z}$, we have $f(x) = x+1$.
So we can now assume $f(x) \neq 0$ for all $x \in \mathbb{Z}$.
If there exists an $y \in \mathbb{Z}$ such that $y=f(y)$, then $f(x) =-1$.
Suppose there exists an $y \in \mathbb{Z}$ such that $f(y)=y$, then with $x=y$
$$f(0) = f(y-f(y)) = f(f(y)) - f(y) - 1 = y-y-1 =-1$$
So we have $f(0)=-1$. Then we have if $f(y+n)=y$ for $n \ge 0$ that
$$f(y+n+1) = f(y+n-f(0)) = f(f(y+n)) -f(0)-1 = f(y) =y$$
So we see that $f(y+n) = y$ for every $n \in \mathbb{N}$.
Now, if $y>0$, we would find with $x=2y$
$$y = f(y)=f(2y -f(y)) = f(f(2y))-f(y)-1 = f(y)-f(y)-1 =-1$$
So $y <0$, and then we have $-1 = f(0) = f(y +(-y)) =y$ and so we find $y=-1$.
Now, we have for all $x \in \mathbb{Z}$
$$-1 = f(0) = f(f(x) -f(x)) = f(f(f(x))) - f(x)-1$$
And so $f(x) = f(f(f(x)))$, and so if $f(-1-k)=-1$ for $k\ge 0$ we have
$$ f(-1-k) = f(-1-k-1 -f(0)) = f(f(-1-k-1)) -f(0)-1 = f(f(-1-k-1))$$
Then we let $f$ act on both sides and we get
$$-1 = f(-1) = f(f(-1-k)) = f(f(f(-1-(k+1)))) = f(-1-(k+1))$$
So we see $f(-1-n)=-1$ for all $n \in \mathbb{N}$.
So we have $f(x) = -1$ for all $x \in \mathbb{Z}$.
A: I think $f$ has to be linear. You derived the expression
$$
f(-f(y)) = f(f(0)) - f(y) -1.
$$
Now let $a=f(0)$ and $t=-f(y)$. Then
$$
f(t) = f(a)+t-1
$$
Edit: plugging in $t=0$ we obtain $f(a)=a+1$, while plugging in $t=a$ we find $a=1$, which gives $f(t)=t+1$, in agreement with what you found.
Edit: As pointed out by Najib Idrissi I did not check for constant solutions. The only constant solution is clearly $f(t)=-1$ as it is promptly inferred from the original equation. However, I believe the expression $f(t) = f(0)+t$ is still the general expression of any non constant solution, regardless of surjectivity. As a matter of fact, we are only interested to see what's the action of $f$ on its range (cause we need to be able to apply $f$ twice). If $f(f(x)) = g(f(x))$ for every $x$, then $f=g$ on $Range(f)$. If after finding $g(x)$ we see that $Range(g)=\mathbb{Z}$, then $f(x)=g(x)$ on $\mathbb{Z}$.
Edit: I finally get completely the point of Najib and Mattia. The expression I found works only if $t$ is in the Range of $f$. Unfortunately, there is no way from there to infer how big $Range(f)$ is. As a matter of fact, it could consist of simply one point. Please, disregard this answer (but keep it as an example of bad reasoning!).
A: Here's a partial solution.
If $0$ is a possible value of $f$, then by taking $f(y) = 0$ we get $f(f(x)) = f(x) + 1$. That is, $f(t) = t + 1$ for $t \in f(\mathbb Z)$, and in particular $f(\mathbb Z)$ contains all nonnegative integers. 
If we define $g(x) = f(x) - x$, the equation becomes
$$ g(x - f(y)) = g(x) + g(x + g(x)) - 1$$
But note that the right side does not depend on $y$.  Thus, since $f(y)$ can be any nonnegative integer, $g$ must be constant, and taking $x = 0$ we see that this constant must be $1$.  So the only solution where $0$ is a possible value of $f$ is $f(x) = x + 1$.
