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

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.