A projection of the 2D square lattice can produce the binary fibbonacci sequence.

This picture I stole from some blog shows this projection:
https://grahamshawcross.files.wordpress.com/2012/04/spots.jp...

--

A 2D square lattice is defined by two perpendicular basis vectors denoting nearest-neighbor distances. Lets put a grid point at the origin at define position as (a,b), where a and b are in units of the basis vectors. That is every integer (a,b) is a grid point that is a hops to the right and b hops up from the origin. Lets also define directions [a,b], where this is the vector from the origin (0,0) to point (a,b).

Consider the following operation: we draw an arbitrary line on the lattice then take all the points within some distance of that line and project them onto the line.

If you draw the line parallel to either basis vector, i.e. [1,0] or [0,1], you will get a 1D sequence where every point is identical: a 1D grid. This is actually independent of the size of the neighborhood around the line we consider as long as it is large enough to include any points; the projections of more distant points align with closer points due to the symmetry of the lattice. A line at 45 degrees (i.e. [1,1]) produces a similar result.

What about some other integer vector? If we draw a line along [5,7], the projected points will no longer be as tidy, but after some distance along the line, we will reach a point equivalent to where we stared: the grid point (5,7). And then (10,14) and (15,21) so on. Every time we hit a new grid point, the pattern of the projection will repeat. The specific pattern between grid points may vary as we change the size of the neighborhood around the line we consider for the projection, but it will always retain the same periodicity. Like the previous cases, as we increase neighborhood size, the projection will stop changing after some critical value as all new points in the neighborhood will line up with previous points. You can see this properties by playing with a piece of graph paper. All rational vectors have parallel integer vectors, and so will have some underlying periodicity.

What about an irrational vector, say [e,pi]? After leaving the origin travelling on this path your will ~never~ hit another grid point. Therefore the projections of grid points will be aperiodic. Not only that, as we increase the neighborhood size, the pattern constantly changes: each new point always has a new spot on the projection. However despite being aperiodic, the system is still ordered: you can know where the next point will show up every time.

It turns out, if you draw a line along the vector [phi,1], where phi is the golden ratio, and use a neighborhood size of sqrt(2), the projection of the points has another interesting property: there are only two possible distances between projected points on the line, lets call them long (L) and short (S), themselves related by the golden ratio. The pattern of Ls and Ss is itself ordered and aperiodic. Not only that, but a simple substituion relation L->LS and S->L produces a longer sequence that includes the original. This just happens to be the substitution relation for finding subsequent terms in the binary fibbonaci sequence.

---

I am sorry for this long-winded explanaton, but I am hoping it helps with visualization without pictures. Perhaps I should write a short blog post with some pictures. The key points are: starting from the origin a rational vector on a grid will always hit another grid point (and then infinite additonal points), which will define periodic relationships will all other grid points to the line. An irrational vector will never hit another grid point, so the relationships are always aperiodic. For a specific choice of projection and vector, you can recover the binary fibbonacci sequence.