SAMC

For $k\ge 0$ we get $$f(k+2)-f(k+1)=\frac{1}{f(k+1)+f(k+2)}$$ hence $f^2(k+2)=f^2(k+1)+1$. It follows $$4=f^2(4)=f^2(3)+1$$ hence $f(3)=\sqrt{3}$. Also, $3=f^2(3)=f^2(2)+1$ implies $$f(2)=\sqrt{2}\text{and}2=f^2(2)=f^2(1)+1$$ gives $f(1)=1$. Finally, $f(1)=\frac{1}{f(0)+f(1)}$ implies $$1=\frac{1}{f(0)+1}$$ hence $f(0)=0$.

Now we prove by induction that for any $n\ge 0$, we have $f(n)=\sqrt{n}$. Assume that $f(k+1)=\sqrt{k+1}$, and get $$f^2(k+2)=f^2(k+1)+1=k+1+1=k+2$$ hence $f(k+2)=\sqrt{k+2}$ and we are done.