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

Question

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.

Answer 1

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.

Answer 2

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.