Cool observation concerning Fibonacci numbers

[AUMathTutor]

I was messing around in class, and I found that there's a small set of rules one can use to draw a directed acylic graph (it looks like a tree, but isn't) such that the number of nodes at a distance d from a "start" node is equal to the (d+1)th Fibonacci number.

The graph is pretty neat looking. Like I said, the graph is infinite and recursively defined (sort of... at least I give an algorithm for producing as large a graph as you want) Maybe the neatest thing about it is its self-similarity and symmetry. I was even able to prove that the property held. I haven't looked into this at all, as in, seen if it's already been done (I'm sure it has) or if it means anything deep (I'm sure it doesn't).

Is this something worth pursuing, or is it just a neat observation that I should let be?

Math is awesome.

 

[Dragonfall]

I'm not sure what it looks like. Can you upload a pic?

 

[AUMathTutor]

Here's a really small, free-hand, example of what it looks like. You can imagine a computer program drawing one a lot better.

 

[junglebeast]

That's pretty cool. It does appear to work!

Basically, you start with a single "leaf" node. Each leaf node will follow the pattern of creating a straight link, followed by a diamond, where the 3 bottom corners of the diamond are new "leaf" nodes. then it just repeats

 

[Dragonfall]

That graph is not acyclic. Why did you choose to connect some nodes and not others?

 

[AUMathTutor]

It's a *directed* acyclic graph. I didn't draw the orientation of the arcs, but I thought it was clear that the orientation is intended to be downward.

And the reason I connected some and not others? I was just messing around, and tried some stuff out. When I saw something that looked interesting, I wrote down the rules used to generate it and it just so happened to work out that way.

I then went back and, using the rules, proved that the number of nodes at a certain distance from the start node was indeed the sequence of Fibonacci numbers.

So, to answer your question, there was no reason for doing it this particular way. I just tried out random stuff and realized that a certain set of rules yielded the above graph, which just so happens to have the property I observed.

 

[AUMathTutor]

"That's pretty cool. It does appear to work!"

Yeah, I know, right? The way I wrote the rules, it's actually startling straightforward to prove. I can post my treatment of it if you'd like to see it.

"Basically, you start with a single "leaf" node. Each leaf node will follow the pattern of creating a straight link, followed by a diamond, where the 3 bottom corners of the diamond are new "leaf" nodes. then it just repeats."

I think I had something like 4 rules (one of which was the base case)... very straightforward, really.

Although I should know better, I'm tempted to count diamonds, edges, etc. and see if I can't get the sequence of prime numbers, or an ASCII message from our alien overlords.

 

[junglebeast]

Although I should know better, I'm tempted to count diamonds, edges, etc. and see if I can't get the sequence of prime numbers, or an ASCII message from our alien overlords.

Haha..well I'm sure you can come up with some curiously unpredictable number sequences, like

1,2,4,5,10,14,25... (See how I did that?)

but then again, you could come up with any random rules for a graph and come up with similar sequences

 

[matheinste]

Haha..well I'm sure you can come up with some curiously unpredictable number sequences, like

1,2,4,5,10,14,25... (See how I did that?)

but then again, you could come up with any random rules for a graph and come up with similar sequences

But it is not unpredictable.

Matheinste.

 

[sylas]

Nice! I love the way the Fibonacci numbers crop up like this in different ways.

The first paper I ever published in maths was on stuff I found fooling around with the Fibonacci numbers; in high school. I've loved them ever since.

 

[AUMathTutor]

"But it is not unpredictable."

Matheinste... does this sequence have some significance, outside of its being the number of edges at a given distance from the start vertex of the graph?

 

[matheinste]

"But it is not unpredictable."

Matheinste... does this sequence have some significance, outside of its being the number of edges at a given distance from the start vertex of the graph?

I am not a mathematician and so was not aware of any significance at all. I just viewed it as the sort of thing you might see in an IQ test or logic puzzle.

The very simple rule predicts the continuation as 38, 64, 101 and so on.

Matheinste.

 

[AUMathTutor]

Hey, I found something else sort of cool.

If you count how many of certain kinds of nodes there are at various levels, you notice a neat pattern. Basically, the sequences are all the same, just shifted or scaled. The sequence is really weird, but definitely related to the Fibonacci sequence by this graph.

And Matheinste: it would be interesting if you (or someone else) saw if what you're seeing corresponds to the graph property that was mentioned. If it does, the rule you see would be a good one to make explicit.

Dude, this is sweet.

 

[mXSCNT]

That's pretty cool. It does appear to work!

Basically, you start with a single "leaf" node. Each leaf node will follow the pattern of creating a straight link, followed by a diamond, where the 3 bottom corners of the diamond are new "leaf" nodes. then it just repeats

So let's prove it is the Fibonacci. There are 4 kinds of nodes at level i, U_i top diamond corners, L_i left diamond corners, R_i right diamond corners, and B_i bottom diamond corners. For i >=1 , we have:
U_{i+1} = B_i + L_i + R_i
L_{i+1} = U_i
R_{i+1} = U_i
B_{i+1} = R_i = L_i = U_{i-1}
Base cases:
L_1 = 1
U_1 = R_1 = L_1 = 0

Let f_i = U_i + L_i + R_i + B_i, the number of nodes at each level
Note f_i = U_{i+1} + U_i = U_{i+1} + L_{i+1}
Now, the fibonacci property would be f_{i+1} = f_i + f_{i-1}. In fact,
f_i + f_{i-1} = U_i + L_i + R_i + B_i + U_i + L_i (using the note)
= L_{i+1} + U_{i+1} + R_{i+1} + B_{i+1}
= f_{i+1}
So, f has the fibonacci property, and its first 2 values match the fibonacci sequence, so by induction it is the fibonacci sequence.

What I think matheinstei meant about 1,2,4,5,10,14,25 is:
4 = (1 + 2) + 1
5 = (2 + 4) - 1
10 = (4 + 5) + 1
14 = (5 + 10) - 1
25 = (10 + 14) + 1

This is a neat graph.

 

[AUMathTutor]

Interesting proof. It's almost the same as mine, except I only used 3 different kinds of nodes... start (S), branch (B), and join (J).

 

[mXSCNT]

Let's generalize a bit--suppose you start with a recursively integer sequence {a_i}, and the question is whether you can write it in a graph like this one. That is, write it in the form:
a_i = \sum_{k=1}^m b_{ki}
b_{ki} = \sum_{j=1}^n b_{f_k(j),i-1}
where the function f_k takes values in {1,2,...,m}, and it is defined on the domain {1,2,...,n}.

Your graph is one such example, now I'll give another. Suppose a_i = a_{i-1} + a_{i-2} + a_{i-3}.
This can be done by letting:
b_{1,i} = b_{1,i-1} + b_{2,i-1} + b_{3,i-1}
b_{2,i} = b_{1,i-1}
b_{3,i} = b_{2,i-1}
Note that b_{1,i} = b_{1,i-1} + b_{1,i-2} + b_{3,i-3}, so if a_i = b_{1,i} + b_{2,i} + b_{3,i} = b_{1,i+1}, we can substitute a_i into the recursive equation about b to prove the example. This general method (writing b_1i as a possibly weighted sum of all the b's, and arranging the remaining b's so that they are b_1i just shifted) works for any linear recurrence with integer coefficients.

I'll leave it to you to draw the graph--but basically you have 3 types of nodes, where the first kind of node has children of the second kind, the second kind has children of the second and third kids, and the third kind has children of the first and second kinds.