# Question: define the height of a tree as the maximum number...

###### Question details

Define the *height* of a tree as the maximum number of
edges between the root and any leaf. We consider the height of an
empty tree to be -1, and the height of a tree consisting of a
single node to be 0.

Prove by induction that every non-empty binary tree of height h
contains fewer than 2^{h+1} nodes.