Size Lower Bounds for Fibonacci Trees


There are many different  proofs the the size is bound below by the
Fibonacci numbers.  Here is yet another one.


Claim: All Fibonacci trees can be generated by the following set of rules.

1) The singleton tree is a Fib-tree
2) The link of 2 Fib-trees is a Fib-tree.
    The two tree must have the same rank and 
    the rank of the new tree is one more than the children.
3) The removal of any child from the root generates a Fib-tree.
    The new rank is one less.
4) The removal of a child from an unmarked non-root parent is a Fib-tree.
    The parent is now marked.


Define the Fibonacci numbers to be

F_0 = 0 F_1 = 1   F_(n+1) = F_n + F_(n-1)

  
Claim:  F_(n+1) <= | Fib-tree of rank n |

Proof:

The proof is by induction on the rank of a tree T.

If the rank is 0 or 1 we are done by inspection.
Let T be a minimal size tree of rank n+1 generated by the rules above.

Consider a sequence S of operation generating T.
Let T' = Link(T_1,T_2) be the last Link in the sequence.
Assume that the rank of T' is minimum over all sequences generating T.
In this case we claim that there will be no rule-3's after T'.

Proof of subclaim: 

The proof is by contradiction. Suppose there was a rule-3 after T'.
There are two case:
1) If we remove T_2 from the tree then we can find a new sequence 
   which does not use this link at all.
2) Consider the case of removing a child of T_1 after T'.
   Since T is of minimum size we will remove a child of T_2 after T'.
   Thus we could have removed these two children before the link and 
   then linked them. This contradicts our assumption that the rank 
   of T' was minimum.

Thus we now know that the rank of T_1 and T_2 is n.
WLOG all the rule-4s can be moved before T' except for the removal of 
a child of T_2. Let T'_2 be the tree of rank n-1 with one child of the 
root removed.

|T| = |T_1| + |T'_2| >= F_(n+1) + F_n  = F_(n+2).

QED