3
$\begingroup$

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.

  • 0
    Please see this link: http://sci.tech-archive.net/Archive/sci.math/2009-01/msg02959.html2010-09-04
  • 0
    See also http://en.wikipedia.org/wiki/Beatty_sequence .2011-06-03

1 Answers 1

2

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.

  • 0
    Thanks, once I got to this intermediate result the rest of it came easily enough.2010-09-08