Converge on square root of 3 with tree.

44 Views Asked by At

If a rule is set for generating a tree whereby: both the children of a node with out-degree 2 each have an out-degree of 3; and the children of a node with out-degree 3 will have out-degrees of 3, 3, 2.

Applied for several generations: this appears to converge on an average out-degree of 1 + square root of 3.

I have not been able to find this result chronicled anywhere with my searching. Is this well known?

1

There are 1 best solutions below

0
On BEST ANSWER

This is an example of a linear homogeneous recurrence relation. If $a(n)$ is the number of vertices in level $n$ with out-degree $2$ and $b(n)$ is the number with out degree $3$, we have $a(n)=b(n-1), b(n)=2a(n-1)+2b(n-1)$ or $b(n)=2b(n-1)+2b(n-2)$. The ratio of successive terms approaches the largest root of $r^2=2r+2$, which is $1+\sqrt 3$