# How can I prove that the number of leaves in a non-empty full K-ary tree is (K − 1)n + 1

A full K-ary tree is a tree where every internal node has exactly K children. Use mathematical induction to prove that the number of leaves in a non-empty full K-ary tree is (K − 1)n + 1, where n is the number of internal nodes.

How can I prove it?

## 1 Answer

A proof indeed is a simple induction with respect to the height $h$ of the tree. Denote by $n_h$ the number of internal nodes of a complete $K$-ary tree and by $l_h$ the number of its leaves. At the base of induction for $h=1$ we have $n_h=1$ and $l_h=K$, so the formula $l_h=(K-1)n_h+1$ is verified. At the induction step each leaf of a tree of height $h$ becomes an internal vertex, but generates $k$ leaves of a tree of a height $h+1$. Thus $n_{h+1}=n_h+l_h$ and $$(K-1)n_{h+1}+1=(K-1)(n_h+l_h)+1=(K-1)n_h+1+(K-1)l_h=Kl_h=l_{h+1}.$$