Let G_n be defined recursively as G_?1=0 and G₀=1 and for n?1, Gn=G_n?1+G_n?2+1.

A binary tree T is height balanced if, for any node in the tree, the height of the left subtree and the height of the right subtree can differ by at most 1. When a tree is height balanced, we can derive a lower bound on the number of nodes.

Prove this claim Using induction: if binary tree T is height-balanced, nodes(T)?G_h(T). (In your proof, you are free to use the following fact, if T is height balanced, then any subtree of T is also height balanced.)