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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – user2884707 Feb 8 '15 at 4:14
  • $\begingroup$ @user2884707: You're welcome. By all means let me know if you get stuck. $\endgroup$ – Brian M. Scott Feb 8 '15 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.