Let $ \alpha$ be the positive root of $ x^{2}-x-1=0$. Then $ \alpha=1+\frac{1}{\alpha}$ and $ \frac{1}{\alpha^{2}}+\frac{1}{\alpha}=1$ Firstly we prove that $ f(n)=\left[\frac{n+1}{\alpha}\right]$. We use induction. The first few values can be easily verified. Suppose that it is true for any $ k\leq n-1$. Then $ f(n-1)=\left[\frac{n}{\alpha}\right]$. Let $ k=\left[\frac{n}{\alpha}\right]$. We must prove that $ \left[\frac{n+1}{\alpha}\right]+\left[\frac{f(n-1)+1}{\alpha}\right]=n$, or $ \left[\frac{n+1}{\alpha}\right]+\left[\frac{k+1}{\alpha}\right]=n$. First case. $ k<\frac{n}{\alpha}<\frac{n+1}{\alpha}<k+1$. Then we must prove that $ E=k+\left[\frac{k+1}{\alpha}\right]=n$. It is clear that $ E$ is an integer. It is sufficient to prove that $ E>n-1$ and $ E<n+1$. Indeed, we have $ k+\left[\frac{k+1}{\alpha}\right]>k+\frac{k+1}{\alpha}-1=k\alpha+\frac{1}{\alpha}-1$. Then $ k\alpha+\frac{1}{\alpha}-1>n-1$ becomes $ k\alpha+\frac{1}{\alpha}>n$ or $ k+\frac{1}{\alpha^{2}}>\frac{n}{\alpha}$. Adding $ \frac{1}{\alpha}$ to both sides we get $ k+1>\frac{n+1}{\alpha}$, which is true by our assumption. For $ E<n+1$ we use $ E<k+\frac{k+1}{\alpha}=k\alpha+\frac{1}{\alpha}<n+1$ since each term of the LHS is smaller than the respective term of the LHS. Second case. $ k<\frac{n}{\alpha}<k+1<\frac{n+1}{\alpha}$. We have to show that $ E=k+1+\frac{k+1}{\alpha}=n$. As in the first case, $ E$ is an integer and we prove that $ n-1<E<n+1$. Indeed $ E<k+1+\frac{k+1}{\alpha}=(k+1)\alpha<n+1$, or $ k+1<\frac{n+1}{\alpha}$, which is true from our assumption. Also $ E>k+1+\frac{k+1}{\alpha}-1=(k+1)\alpha-1>\frac{n}{\alpha}\cdot\alpha-1=n-1$, also from our assumption. Now, clearly $ g$ has degree 1. Let $ g=ux+v$. Since $ f(n)=\left[\frac{n+1}{\alpha}\right]=\left[g(n)\right]$, we get $ \left|n\left(\frac{1}{\alpha}-u\right)+\frac{1}{\alpha}-v\right|<1$. Clearly $ u=\frac{1}{\alpha}$. Then using the density of $ \left\{\frac{n}{\alpha}\right\}$ in $ (0,1)$ we see that $ v=\frac{1}{\alpha}$. So $ g(n)=\frac{n+1}{\alpha}$.