Fibonacci tree (source code)

= Fibonacci tree
{c}

A <Fibonacci tree> is a recursively defined <binary tree> whose two subtrees have consecutive smaller orders. One convention <sets> $T_0$ and $T_1$ to a single vertex and defines $T_n$ for $n\geq2$ by attaching $T_{n-1}$ and $T_{n-2}$ to a new root. Then its vertex count satisfies $N_n=1+N_{n-1}+N_{n-2}$, so $N_n=2F_{n+1}-1$ for <Fibonacci numbers> $F_0=0,F_1=1$. The counts begin $1,1,3,5,9$. Initial <trees> vary across applications, so the convention must be stated; the common feature is the consecutive-order recursive branching.