0

In order to compute any Fibonacci number, you need the previous two terms in the series. This continues recursively until a base case is reached. From this, a binary tree can be constructed. The top node N, will have subnodes N-1 and N-2. The leaves of the tree will be all 1's and 2's. Since this tree is a fractal, it should have a Hausdorff dimension between 1 and 2. The number of elements E(N) in the tree as a function of N is:
N : E(N)
1 : 1 (base case)
2 : 1 (base case)
3 : 3
4 : 5
5 : 9
6 : 15
7 : 25
8 : 41
9 : 67
10 : 109
...
N : E(N-1)+E(N-2)+1

This grows exponentially. I figured if I were to use the formula E(N) = N^D, I could calculate the dimension. Or D = log(N(E))/log(N). However I am failing to get any reasonable solution. Personally, I'm hoping I get phi, but I'm not holding my breath.

flag
"Since this tree is a fractal, it should have a Hausdorff dimension between 1 and 2." Could you please explain your justification for this claim, in more detail? – Yemon Choi Feb 3 2012 at 1:37
4 
 To talk about Hausdorff dimension, you need a metric. What metric are you using on your tree? – unknown (google) Feb 3 2012 at 1:51
The name is spelled Fibonacci, not Fibonnaci. – Angelo Feb 3 2012 at 5:53
Same reason the a DLA (en.wikipedia.org/wiki/…) has a dimension between 1 and 2. It's somewhere between a line and a plane. – Chet Feb 3 2012 at 5:53
As far as a metric, I would assume 2D Euclidian space. I don't know if that even answers your question, I don't delve too deep into theoretical math, I just find fractals to be interesting. I am envisioning a tree with two branches leaving each node. The branches can have unit length. This was something I had not initially considered, I could be overlooking some things still. – Chet Feb 3 2012 at 5:58
show 2 more comments

closed as not a real question by Will Jagy, Yemon Choi, Emil Jeřábek, Andreas Blass, Bill Johnson Feb 3 2012 at 14:01

Browse other questions tagged or ask your own question.