A strictly $k$-ary tree is a $k$-ary tree (a binary tree is a $2$-ary tree) in which every node has either no children (is a leaf) or $k$ children. A complete $k$-ary tree of depth $n$ is a strictly $k$-ary tree in which every node on levels $1, 2, \ldots, n-1$ is a parent, and each node on level $n$ is a leaf. Prove using mathematical induction that every complete $k$-ary tree of depth $n$ has $(k^{n+1}–1)/(k-1)$ nodes for all integers $n\ge 0$. Assume that $k\ge 2$.
I don't where to start!
Best Answer
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)$.