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?
[Math] How to prove that the number of leaves in a non-empty full K-ary tree is (K − 1)n + 1
graph theoryinductiontrees
Related Solutions
My preferred definition of a non-empty, full binary tree is:
Definition 0. A pointed magma is an ordered triple $(X,\bullet,\star)$, such that:
- $X$ is a set
- $\bullet$ is an element of $X,$ and
- $\star$ is a function $X \times X \rightarrow X$.
Definition 1. Write $\mathbb{T}$ for the initial pointed magma, the elements of which are called non-empty full binary trees.
For example, here's an example of a non-empty full binary tree:
$$(\bullet \star \bullet) \star \bullet \in \mathbb{T}$$
This can be visualized as a tree, of course:
Okay. Let $\varphi : \mathbb{T} \rightarrow \mathbb{N}$ denote the node-counting function. Explicitly:
Definition 2. Define a function $\oplus : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ as follows: $$a\oplus b = a+b+1$$
Definition 3. Let $\varphi : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,\oplus)$ denote the unique such homomorphism of pointed magmas. We call $\varphi$ the node counting function.
For example, $$\varphi((\bullet \star \bullet) \star \bullet) = (1\oplus 1) \oplus 1 = 3 \oplus 1 = 5$$
So the above tree has $5$ nodes, as desired.
I claim that:
Claim. For all $x \in \mathbb{T}$, the natural number $\varphi(x)$ is odd.
This prove this, we need a way of performing induction on non-empty full binary trees. Here's a theorem that lets us do this:
Structural Induction for $\mathbb{T}$.
The pointed magma $(\mathbb{T},\bullet,\star)$ has no proper subalgebras.
More explicitly:
Structural Induction for $\mathbb{T}$. (Long form.)
Let $X$ denote a subset of $\mathbb{T}$.
If
- $\bullet \in X$, and
- for all $x,y \in X$, we have $x \star y \in X$,
then
$X = \mathbb{T}$.
Now we can prove our claim. Let $X$ denote the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd.
We know that $\bullet \in X$, since $\varphi(\bullet) = 1$ and $1$ is odd.
Assume $x,y \in X$. We will show that $x \star y \in X$. We know that $\varphi(x \star y) = \varphi(x) \oplus \varphi(y) = \varphi(x)+\varphi(y)+1.$ But the sum of three odd numbers is itself odd. So $\varphi(x \star y)$ is odd.
Hence by the structural induction theorem, we have $X=\mathbb{T}$. But recall that we defined $X$ as the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. Thus $\mathbb{T}$ itself is the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. In other words, $\varphi(x)$ is always odd, for all $x \in \mathbb{T}$. QED
A further comment.
It is worth noting that we can define the leaf-counting function in much the same way:
Definition 4. Let $\lambda : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,+)$ denote the unique such homomorphism of pointed magmas.
We call $\lambda$ the node counting function.
For instance, $$\lambda((\bullet \star \bullet) \star \bullet) = (1+1)+1 = 3,$$ so the aforementioned tree has $3$ leaves, as desired.
The cool thing about $\lambda$ is that it gives what is perhaps the most fundamental definition of the Catalan numbers; namely, writing $C_n$ for the $n$th Catalan number, we can define: $$C_n = |\lambda^{-1}(n+1)|$$
For example, $$C_2 = |\lambda^{-1}(3)| = |\{(\bullet \star \bullet) \star \bullet, \bullet \star (\bullet \star \bullet)\}| = 2$$
Follow the standard pattern of a proof by mathematical induction. Since you’re trying to prove a result for each $n\ge 0$, your base case is $n=0$: you must verify that a complete $k$-ary tree of depth $0$ has $$\frac{k^{0+1}-1}{k-1}=\frac{k-1}{k-1}=1$$ nodes. Then assume as your induction hypothesis that every complete $k$-ary tree of depth $n$ has $$\frac{k^{n+1}-1}{k-1}$$ nodes and try to use that hypothesis to prove that every complete $k$-ary tree of depth $n+1$ has
$$\frac{k^{(n+1)+1}-1}{k-1}=\frac{k^{n+2}-1}{k-1}$$
nodes. To do this, suppose that $T$ is a complete $k$-ary tree of depth $n+1$. You know that it consists of a complete $k$-ary tree $T_0$ of depth $n$ plus a level consisting entirely of leaves. By the induction hypothesis there are $$\frac{k^{n+1}-1}{k-1}$$ nodes in $T_0$. Suppose that there are $\ell$ leaves; then you want to show that
$$\frac{k^{n+1}-1}{k-1}+\ell=\frac{k^{n+2}-1}{k-1}\;.\tag{1}$$
In order to do this, you’ll have to figure out what $\ell$ is. If you don’t already know, I suggest that you draw complete $k$-ary trees of depth $3$ or $4$, say, for $k=2$ and $k=3$ and see how many nodes are in each level. The sizes of the levels in a complete $k$-ary tree grow in a very simple fashion, and once you spot the pattern, it’s very easy to prove by induction that it really does hold. And once you know what $\ell$ is in terms of $k$ and $n$, it’s pretty easy to verify $(1)$.
Related Question
- [Math] In binary tree, number of nodes with two children when number of leaves is given
- [Math] Full 4-ary tree with 58 internal nodes
- [Math] Full binary tree proof validity: Number of leaves $L$ and number of nodes $N$
- [Math] Is the proof that, the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree, correct
Best 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}.$$