A specific and interesting recurrence relation

Question

Let f and g be increasing functions such that the sets {f(1),f(2),...} and {g(1),g(2),...} partition the positive integers. Suppose that f and g are related by the condition g(n)=f(f(n))+1 for all $n>0$. Prove that f(n)=[nФ] and $g(n)=[nФ^2]$.Where $Ф=(1+√5)/2$ and [x] is the greatest integer n such that $x⩾n$.

My question is not about how to prove it. Instead, let's suppose that the question ask you to find the expression of f and g but won't tell you the explicit formulas of them. The task becomes much more harder. All the detail I find for this is to guess a formula of f and g then to verify it without solve it, like what the question want us to do. It seems there is no general algorithm to tackle this kind of "devil recurrence". So I am curious about how people can find such a simple and beautiful expressions of f and g, what process and clue did they follow? Can someone give me some historical background about my question in detail? Thanks in advance!

Answer 1

These sequences are called Beatty sequences. For your specific pair of sequences, they are OEIS sequence A001950 and OEIS sequence A000201. Quoting Wikipedia:

In mathematics, a Beatty sequence (or homogeneous Beatty sequence) is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.

Rayleigh's theorem, named after Lord Rayleigh, states that the complement of a Beatty sequence, consisting of the positive integers that are not in the sequence, is itself a Beatty sequence generated by a different irrational number.