# Proof of closed form Hofstadter G-Sequence

I'm working through a discrete maths text book and was stumped as to how to prove the closed form solution of the Hofstadter G-Sequence
$a(0) = 0$ and $a(n) = n - a(a(n-1)), n \geq 1$

The closed form is $a(n) = \lfloor(n+1)\mu\rfloor$ where $\mu$ is the inverse of the golden ratio.

The text book says to prove the following two statements on the way to proving this.
Show that $n\mu -\lfloor n\mu \rfloor + n\mu^2 - \lfloor n\mu^2 \rfloor = 1$ for all n > 0
Show that $\lfloor(1+\mu)(1-\alpha)\rfloor + \lfloor\alpha+\mu\rfloor = 1$ for all $\alpha \in R, 0 \leq \alpha < 1\space and\space \alpha \ne 1-\mu$

I'm relatively certain I was able to confirm those those two statements but I'm not sure where to apply them when I start on the main proof. I think it's just my weakness with algebra, particularly how to deal with the floor that's holding me up.

-
Please see this link: sci.tech-archive.net/Archive/sci.math/2009-01/msg02959.html – anonymous Sep 4 '10 at 3:31
– Qiaochu Yuan Jun 3 '11 at 22:14

Our goal is to prove $$\lfloor \mu (n+1)\rfloor = n-\lfloor \mu \lfloor \mu n+1\rfloor \rfloor.$$
If you can prove $\lfloor \mu \lfloor \mu n+1\rfloor \rfloor = \lfloor (1-\mu ) (n+1)\rfloor$ then you should be able to prove the above without too much effort.