# Finding $f(n)=f(f(n-1))+f(f(n+1))$

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.

• You should rule out the case $n=1$, for which the formula does not apply, as $f(n-1)$ is not defined. – AndreasT Nov 28 '15 at 23:53
• 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. – Cataline Nov 28 '15 at 23:54
• 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. – 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$

• 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}$. – user236182 Nov 29 '15 at 0:36
• The answer is "there are no such functions $f$", as shown in I. Cavey's solution. – user236182 Nov 29 '15 at 0:36
• 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? – Cataline Nov 29 '15 at 0:37
• $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. – user236182 Nov 29 '15 at 0:42
• 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. – Piquito Nov 29 '15 at 4:08