OBM 2006 Problem 6

Professor Piraldo takes part in soccer matches with a lot of goals and judges a match in his own peculiar way. A match with score of $m$ goals to $n$ goals, $m\geq n$ , is tough when $m\leq f(n)$ , where $f(n)$ is defined by $f(0) = 0$ and, for $n \geq 1$ , $f(n) = 2n-f(r)+r$ , where $r$ is the largest integer such that $r < n$ and $f(r) \leq n$ .

Let $\phi ={1+\sqrt 5\over 2}$ . Prove that a match with score of $m$ goals to $n$ , $m\geq n$ , is tough if $m\leq \phi n$ and is not tough if $m \geq \phi n+1$ .