# Functions satisfying $f:\mathbb{N}\rightarrow\ \mathbb{N}$ and $f(f(n))+f(n+1)=n+2$

Find all functions $f$ such that $f:\mathbb{N}\rightarrow\ \mathbb{N}$ and $f(f(n))+f(n+1)=n+2$

Let us plug in $n=1$

$f(f(1))+f(2)=3$

Since the function is from $\mathbb{N}$ to $\mathbb{N}$, $f(2)$ can only take the values $1,2$. Now we divide the problem into cases.

Case-1: $f(f(1))=2,f(2)=1$

We can assume that $f(1)=c$ for the time being. Then plugging in $n=3$ and using $f(2)=1$ gives $$f(3)=4-c$$ and again since the range of the function is positive integers,then $4-c$ has to be positive and hence $c$ belongs to {$1,2,3$}. Now, $$f(1)=c$$$$\implies f(f(1))=f(c)$$$$\implies 2=f(c)$$ by the assumption that $f(f(1))=2$ . Now,since $c$ can only take the values $1,2,3$,we start treating cases. If $c=1$,$$f(c)=2$$$$\implies f(1)=2$$ but we know from the deinition of $c$ that $f(1)=c=1$,a contradiction.If $c=2$,then $2=f(c)=f(2)$ but $f(2)=1$ by assumption. Finally,if $c=3$ $$2=f(c)=f(3)$$ but $$f(3)=4-c=4-3=1$$ which is once again a contradiction. Therefore there are no such functions in this case.

Case-2: $f(f(1))=1,f(2)=2$

Again assuming $f(1)=c$ and using $f(n)\le n$ along with plugging $n=c-1$ will give us that $f(1)=1$ and then it is easy to prove that such a function exists by recursion. I can only give a "sort of recursive" way to define the function. Here it goes $$f:\mathbb{N}\rightarrow \mathbb{N}$$$$f(1)=1$$$$f(n)=n+1-f(f(n-1))$$

But this case is harder to deal with.Some help will be appreciated.

• Also,the first few values starting from n=1 are $1,2,2,3,4,4,5,5,6,7,7,8,9,9,10$. I have tried proving that the function is non-decreasing,but have failed.It is perhaps too much to say the values don't follow any pattern,but I cannot see any pattern that will help me find a closed form expression.It might also help to prove that the function is surjective(onto). – rah4927 Jan 9 '15 at 17:52
• OEIS is your friend! OIES A019446 $a(n) = \left\lceil \frac{n}{\phi} \right\rceil$ where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ration matches your sequence (at least up to $n = 100$). – achille hui Jan 9 '15 at 18:27
• Since you are asked to "find all functions $f$", isn't it sufficient to show that there is only one such function, and it is uniquely determined by the given recursion? (The fact that the recursion works follows from $f(n)\le n$, which is easily proved via induction.) – user856 Jan 9 '15 at 18:27
• @Rahul,yes it is.But I am extremely curious how we could have come up with the achille hui's OEIS solution above. – rah4927 Jan 9 '15 at 18:32
• @achille,interesting.I suppose the presence of a floor or ceiling was expected,given the nature of the values.Any ideas how we could have come up with it?Thanks for the OEIS link btw. – rah4927 Jan 9 '15 at 18:34

This answer doesn't attempt to solve following functional equation from first principle.

$$f(n+1) + f(f(n)) = n+2,\quad\text{ for } n \ge 1\tag{*1}$$

Instead, it verify the function $\left\lceil \frac{n}{\phi}\right\rceil$ appeared in OEIS A019446 is a solution of $(*1)$.

For any fixed $n \ge 1$, since $\phi$ is irrational, there exists 3 numbers $\epsilon_1,\epsilon_2,\epsilon_3 \in (0,1)$ such that: $$\left\lceil \frac{n+1}{\phi} \right\rceil = \frac{n+1}{\phi} + \epsilon_1, \quad \left\lceil \frac{n}{\phi} \right\rceil = \frac{n}{\phi} + \epsilon_2, \quad\text{ and }\quad \left\lceil\frac{1}{\phi}\left\lceil \frac{n}{\phi} \right\rceil\right\rceil = \frac{1}{\phi}\left\lceil \frac{n}{\phi} \right\rceil + \epsilon_3$$

Substitute this into $(*1)$, this is equivalent to showing:

$$\left( \frac{n+1}{\phi} + \epsilon_1 \right) + \frac{1}{\phi}\left(\frac{n}{\phi} + \epsilon_2\right) + \epsilon_3 \stackrel{?}{=} n + 2 \iff ( \frac{1}{\phi} + \epsilon_1 ) + \frac{\epsilon_2}{\phi} + \epsilon_3 \stackrel{?}{=} 2$$ There are two possible cases:

• If $\epsilon_2 < \frac{1}{\phi}$,

$$\frac{n+1}{\phi} > \left\lceil\frac{n}{\phi}\right\rceil \implies \frac{1}{\phi} + \epsilon_1 = \epsilon_2 + 1 \implies \left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} = \phi \epsilon_2 + 1 \in (1,2)$$

• If $\epsilon_2 \ge \frac{1}{\phi}$, $$\frac{n+1}{\phi} \le \left\lceil\frac{n}{\phi}\right\rceil \implies \frac{1}{\phi} + \epsilon_1 = \epsilon_2 \implies \left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} = \phi\epsilon_2 \in [1,\phi)$$

In both cases, since $\epsilon_3 \in (0,1)$, we have $$\left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} \in [1,2) \implies \left( \frac{1}{\phi} + \epsilon_1 \right) + \frac{\epsilon_2}{\phi} + \epsilon_3 \in (1,3)$$ Since by construction, the LHS of this expression is an integer, it has to be $2$ and hence $(*1)$ is satisfied.

So we start by the fact that $f(k) ≤ k$ for any $k$ and we can determine using strong induction on $n$ the value of $f (n)$ : if we have known $f(1),f(2),...,f(k)$ then by setting $n = k + 1$ we compute $f(k + 1)$. (This is already mentioned above)

But this (strong induction) implies that $f$ is defined uniquely

And, as was shown in the first answer, The function $f(x) = [cx]+1$ where $c = \frac{√5−1}{ 2}$ is a solution, hence it's the only solution.