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$


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.

  • $\begingroup$ 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). $\endgroup$ – rah4927 Jan 9 '15 at 17:52
  • 2
    $\begingroup$ 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$). $\endgroup$ – achille hui Jan 9 '15 at 18:27
  • 2
    $\begingroup$ 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.) $\endgroup$ – user856 Jan 9 '15 at 18:27
  • $\begingroup$ @Rahul,yes it is.But I am extremely curious how we could have come up with the achille hui's OEIS solution above. $\endgroup$ – rah4927 Jan 9 '15 at 18:32
  • $\begingroup$ @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. $\endgroup$ – 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.


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.