Q:

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. 

A:

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. 

A:

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.