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?

  • 6
    $\begingroup$ There is the trivial $f(x)=0$ $\endgroup$ – kingW3 Mar 12 '17 at 18:04
  • $\begingroup$ I guess OP is looking for the proof for non-trivial cases... $\endgroup$ – VanDerWarden Mar 12 '17 at 20:36

$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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.