Derive a formula for the nth term of a sequence (most likely a Beatty sequence) In this MIT Putnam seminar problem set, the following question can be found (it's problem 8):

Define a sequence $a_1 < a_2 < · · ·$ of positive integers as follows. Pick $a_1 = 1$. Once $a_1, . . . , a_n$ have been chosen, let $a_{n+1}$ be the least positive integer not already chosen and not of the form $a_i +i$ for $1 \leq i \leq n$. Thus $a_1 + 1 = 2$ is not allowed, so $a_2 = 3$. The first few terms of the sequence are $1,3,4,6,8,9,11,12,14,16,17,19,....$. Find a simple formula for $a_n$. Your formula should enable you, for instance, to compute $a_{1,000,000}$.

I tried to look for pattern but I could not find any. After I looked at OEIS, it seems to be a Beatty sequence $a_n = \lfloor n\phi \rfloor$ where $\phi = \frac{\sqrt{5}+1}{2}$.
I am wondering how one could "derive" the formula. It is quite odd that the derivation gives greatest integer function of a number as an answer!
 A: When we saw this problem years ago, the idea was to involve Beatty sequences. IIRC, We couldn't solve it without using Beatty sequences (or its ideas in some form).
Here's how the wishful thinking went:

*

*Let the sequence be $a_n$.

*Define $ b_n = a_n + n$, which is the complement.

*IF (and that's a big wishful if) $a_n = \lfloor \alpha \times n \rfloor$, then $b_n = \lfloor (\alpha+1)n\rfloor$

*Hence, invoking Beatty sequences, we want $\frac{1}{\alpha} + \frac{1}{ \alpha + 1 } = 1$ for positive irrational $ \alpha$.

*This gives $ \alpha = \frac{ \sqrt{5} + 1 } { 2}$ .

*It remains to verify that $ a_n, b_n$ are indeed these sequences, which you use Beatty sequence proof again to demonstrate.

A: Comments only:
Since you have already known the answer, the following is just hindsight.  First of all we know that $\{ a_n \}$ and $\{ b_n = a_n+n \}$ is a partition of $\mathbb N$. On the other hand if a formula of $\{ a_n \}$ ensures that $\{a_n\}$ and $\{a_n+n\}$ partition $\mathbb N$ then we are done (Edit: not quite, we still need $a_{n-1}+n-1>a_n$, but the formula we derive indeed satisfies this condition.)
Next, it's probably natural (hindsight of course) to conjecture that the proportion of $\{ a_n \}$ and $\{ b_n \}$ are asymptotically constant, i.e.,
$$\lim_{n\to\infty} \frac{n}{a_n} = \alpha, \lim_{n\to\infty} \frac{n}{b_n}=1 -\alpha \\
\implies 1-\alpha = \lim_{n\to\infty} \frac{\frac{n}{a_n}}{1+\frac{n}{a_n}}=\frac{\alpha}{1+\alpha}\implies \alpha = \frac{1+\sqrt 5}{2}$$
By examining a number of $a_i$'s and $b_i$'s we further conjecture
$$a_n = \left\lfloor \alpha n\right\rfloor$$
Finally, we can apply either one of the proofs of the Rayleigh_theorem to conclude $\{a_n\}$ and $\{ b_n \}$ indeed partition $\mathbb N$.
