Question 6.12 from the course text.
case n=1: Leaves = K = (K-1)1 + 1 = (K-1)n + 1
Now suppose that the formula holds for n=m. We will show that it also holds for n=m+1.
case n=m+1:
If we have m internal nodes, then to increase the number of internal
nodes by 1, we convert a leaf node to an internal node. In the process of
doing this, K new leaves will be added since the tree has to be full. Thus,
a total of (K-1) leaves will be added.
Leaves(m+1)
= Leaves(m) + (K-1)
= (K-1)(m) + 1 + (K-1)
= (K-1)(m+1) + 1
Hence, by mathematical induction, the formula holds for all n.