Proof by induction.

Question

Proof by induction that maximum number of leaves in m-subtree of height h is at least m^h 

Answer 1

The statement is usually meant in a stronger and more standard form: in an m-ary tree of height h, the maximum number of leaves is m^h, which implies it is also at least mh for h >= 1. This can be proven using induction. For the base case, when h = 0, the tree consists of just the root, so there is exactly one leaf, and 1 = m^0, so the claim holds. For the inductive step, assume that any m-ary tree of height k has at most m^k leaves. Now consider a tree of height k + 1: its root can have at most m children, and each child is the root of a subtree of height at most k. By the inductive hypothesis, each subtree has at most m^k leaves, so the total number of leaves is at most m * m^k = m^(k + 1). This completes the induction, showing the maximum number of leaves is m^h. Since exponential growth dominates linear growth, m^h >= mh for h >= 1, so the original statement follows as a weaker consequence.