Prove that there is no function $f:\mathbb{Z}_{\ge 0}\rightarrow \mathbb{Z}_{\ge 0}$ such that $f(f(n-1))=f(n+1)-f(n)$

Question

Prove that there is no function $f:\mathbb{Z}_{\ge 0}\rightarrow > \mathbb{Z}_{\ge 0}$ such that $f(f(n-1))=f(n+1)-f(n)$ for $n\ge 2$

Well, any hints?

Answer 1

$f(f(x-1))=f(x+1)-f(x) \tag{1}$

First we rule out the trivial solution $f(x)=0$.

The function cannot be decreasing anywhere where $x \ge 2 $ because that would lead to negative function values because : $f(f(x-1))=f(x+1)-f(x)$. If the right hand side of this equation becomes negative that would imply (left hand side) that the function becomes negative somewhere.

Let's assume $f(x)$ is strictly increasing beyond a certain point (say beyond $x=b$ ).
Then we can find $c >b$ for which $f(c)>b$. So : $ f(c+1) > f(c) >b \implies $
$ f(f(c+1)) > f(f(c)) \implies f(c+3)-f(c+2) > f(c+2)-f(c+1) $
This means that the difference between consecutive function values must also be strictly increasing beyond a certain point ($f(x)$ increases faster than $x$). So for large enough $q$ we find : $f(q)>q+2$. Now : $f(f(q)) > f(q+2) $ but also : $f(f(q)) =f(q+2)-f(q+1)$ which would mean $f(q+1)$ must be negative. This leads to a contradiction.

So for every $N$ there must be some $M > N$ for which : $f(M+1)-f(M)=0$ because $f()$ can't be decreasing and it can't be strictly increasing beyond any point. This means we can find arbitrarily large $M-1$ for which $f(f(M-1))=0$. So $f()$ must be decreasing somewhere or it must be constant $0$. Therefore we cannot find such function.

Update . Some extra explanation for the last step :

Above we ruled out trivial solutions like $f(x)=0$. It turns out there are also other 'more or less trivial' solutions.

We can choose values for $f(0),f(1)$ and $f(2)$ more or less arbitrarily. We know at least one of $f(0),f(1)$ and $f(2)$ must be $0$ because we must have $f(f(M-1))=0$ for some arbitrarily large $M$ (mentioned above) and $f()$ can not be decreasing beyond $x=2$.

Below we distinguish some cases:

A : $f(0)=0, f(1),f(2)>0$. Now $f(f(M-1))=0$ implies $f(M-1)=0$ , this can only be when $f(x)$ is zero everywhere because $f()$ is non-decreasing.
B : $ f(1)=0,f(2)>0$. This implies $f(M-1)=1$ exists for arbitrarily large $M$. So the function can never be greater than $1$ when $x>2$. In fact $f(0)=0,f(1)=0,f(2)=1,f(3)=1$ etc. is a valid solution.
C : $ f(2)=0,f(3)>0 $. In this case all possibilities lead to a strictly increasing solution (which can't exist).