Determine whether a function exists from the positive integers to the positive integers which satisfies the equation: $$f(n)=f(f(n-1))+f(f(n+1))$$.

My guess is that this function does not exist, as through trial and error I found that $f(n)=\frac{n}{2}$ is a solution to the functional equation. Obviously this is not enough, but I don't know how to tackle this problem.

I found that $f(n+2)-f(n)=f(f(n+3))-f(f(n-1))$, but this doesn't seem very useful to me.
Can anyone help me with this problem?


Here is a sketch of the proof that no such function exists. Say that such a function does exist. Take $n$ be such that $f(n)=m$ is the minimum value that $f$ takes. If $n\neq1$, then then $m$ is expressed as the sum of two outputs of the function $f$ by the given relation. Since the outputs of $f$ are positive integers, this is impossible.

If the minimum is $f(1)$ and is attained only at $1$, then take let $n_1>1$ be such that $f(n_1)$ is the minimum of the values attained by $f$ excluding $f(1)$. Then $f(n_1+1)\geq f(n_1)>f(1)\geq 1$, so by the minimality of $f(n_1)$, we have that $f(f(n_1+1))\geq f(n_1)$. Again this leaves the desired relation impossible, so there is no such function.

  • $\begingroup$ You should rule out the case $n=1$, for which the formula does not apply, as $f(n-1)$ is not defined. $\endgroup$ – AndreasT Nov 28 '15 at 23:53
  • $\begingroup$ Thanks for the quick response and good answer! But on that note, what would I have to do to turn this answer from a sketch to a full proof? It seems fairly complete to me. $\endgroup$ – Cataline Nov 28 '15 at 23:54
  • $\begingroup$ For starters, address the good point that @AndreasT raises about the case that the minimum is $f(1)$ and is attained only there. I will edit to address this case. $\endgroup$ – I. Cavey Nov 28 '15 at 23:59

The function $f(x)=\frac{x}{2}$ is linear of $\mathbb R$ in $\mathbb R$ and satisfies the question but for all $\mathbb R$

$$f(x+1)= \frac {x+1}{2}\Rightarrow f(f(x+1))=\frac{x+1}{4}$$

$$f(x-1)= \frac {x-1}{2}\Rightarrow f(f(x-1))=\frac{x-1}{4}$$

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

Since f is linear, one has $$f(x)=f(\frac{x+1}{2})+f(\frac{x-1}{2})=\frac{x+1}{4}+\frac{x-1}{4}=\frac{x}{2}$$ for all real.

Thus $f(x)=f(f(x+1)) +f(f(x-1))$ for $x\in \mathbb R$

  • $\begingroup$ But $f(x)$ has to be $\Bbb Z^+\to \Bbb Z^+$. I.e. with domain $\Bbb Z^+$ and co-domain $\Bbb Z^+$. In particular, $f(1),f(2),f(3),\ldots\in\Bbb Z^+$. Not when $f(x)=\frac{x}{2}$. $\endgroup$ – user236182 Nov 29 '15 at 0:36
  • $\begingroup$ The answer is "there are no such functions $f$", as shown in I. Cavey's solution. $\endgroup$ – user236182 Nov 29 '15 at 0:36
  • $\begingroup$ Not too sure what you're doing here. All it seems you have done is verify that $f(x)=\frac{x}{2}$ satisfies the functional equation, which is not what I wanted. Perhaps you could provide more verbal explanation? $\endgroup$ – Cataline Nov 29 '15 at 0:37
  • $\begingroup$ $f(x)=\frac{x}{2}$ is a solution if the function has the domain $\Bbb R$ and the codomain $\Bbb R$. In this case we're working in $\Bbb Z^+$, not in $\Bbb R$, and there are no solutions in this case. $\endgroup$ – user236182 Nov 29 '15 at 0:42
  • $\begingroup$ I have edited before read these four comments I read just now (I realized it was a mistake). Something to say: the rule is valid for rational numbers and restriction to a subset becomes of less interest. As a result this question is not relevant. $\endgroup$ – Piquito Nov 29 '15 at 4:08

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.