0
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thank you for putting so much effort in this. I really appreciate your answer. Thanks a lot. I'll try it let you know if I get stuck. :D $\endgroup$ Commented Feb 8, 2015 at 4:14
  • $\begingroup$ @user2884707: You're welcome. By all means let me know if you get stuck. $\endgroup$ Commented Feb 8, 2015 at 5:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .