In: Advanced Math
Prove that a full m-ary tree of height h has at least h(m − 1) leaves.
The correct statement is: a full -ary tree of height has at least
We use induction on .
If , then a full -ary tree of height consists of a root and children all of whom are leaves. Thus, the number of leaves is .
Suppose that for some integer it is true that every full -ary tree of height at most has at least leaves. Consider a full -ary tree of height , and consider the subtree obtained by deleting all the leaves of which are at height . Since we are not deleting any of the internal nodes of or any leave at height , the resulting subtree is full -ary tree of height , and by induction hypothesis, this resulting subtree has at least leaves. In some of these are internal nodes (because the leaves at height , of which there is at least one, are connected to some of these nodes), hence, we get at least
leaves. Thus, the number of leaves is at least . Since , we get .
Thus, we have proved, by induction, that a full -ary tree of height has at least leaves.