3. The function $f$ is defined on the set of non-negative integers $\mathbb{N}_{0}=\mathbb{N} \cup\{0\}$, and takes values in the same set $\mathbb{N}_{0}$. For every $n \in \mathbb{N}_{0}$, it holds that $f(f(n))+f(n)=2 n+3$. Find $f(2012)$.
Solution. For $n=0$ we have $f(0)+f(f(0))=3$, so considering that $f(f(0)) \geq 0$, it follows that $0 \leq f(0) \leq 3, f(0) \in \mathbb{N}_{0}$.

a) Let $f(0)=0$, then $f(f(0))=f(0)=0$. Thus, $3=f(0)+f(f(0))=0$, which is a contradiction. Therefore, $f(0) \neq 0$.

b) Let $f(0)=1$. Then $f(f(0))=f(1)=2$. From

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

we get that $f(2)=3$. By induction, we will show that $f(n)=n+1$. Suppose the statement is true for $k \leq n$, i.e., $f(k)=k+1$. Then

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

From here, $f(k+1)=k+2$, so by the principle of mathematical induction, $f(n)=n+1$ for every $n$. According to this, $f(2012)=2013$.

c) Let $f(0)=2$. Then $f(2)=1$, so

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

It follows that $f(1)=6$. However, $5=f(1)+f(f(1))$, from which $f(1) \leq 5$, which is a contradiction.

d) Let $f(0)=3$. Then $f(3)=0$. But,

$$
3=f(0)+f(f(0))=f(0)+f(3)=f(3)+f(f(3))=9
$$

so this is again a contradiction.

Therefore, $f(n)=n+1$, and $f(2012)=2013$.