How to prove $\sum_{i=1}^{k}2^{-d_i} \leq 1$

Question

The question is:

In a binary tree, the depths of leaf nodes are $d_1, d_2,... d_k.$ Prove that $\sum_{i=1}^{k}2^{-d_i} \leq 1$

Understand why this is true, in that: If a tree has only 1 node, it has one leaf, and thus $\sum_{i=1}^{1} = 2^{-1} = 1 \leq 1$

If a tree has 3 nodes, the tree has two leaves, and: $2^{-1} + 2^{-2} = \frac{1}{2} + \frac{1}{2} \leq 1$

and so on...

I started this thinking that I could use induction to prove it.

So:

Base Case: Let $n = 1$, which as shown above $\leq 1$.

What is the inductive step here? Should I use induction?

Answer 1

Take any arbitrary tree, and add a child leaf to any non-leaf node with only one child. This can only increase $\sum 2^{-d_i}$, because you're adding leaves without changing the degree of any existing leaf, or changing any existing leaf to a non-leaf.

Now find each node with two child leaf nodes. From each of these, remove both leaves. This gets rid of two leaf nodes with degree $d$ and creates a new leaf node with degree $d-1$, leaving $\sum 2^{-d_i}$ unchanged.

Repeat until all that's left is the trivial one-node tree, for which $\sum 2^{-d_i} = 1$.

Answer 2

Prove it by structural induction on the tree (or if you like, by induction on the depth of the tree). Let $S(T)$ denote $\sum 2^{-d_i}$ for leaf nodes of the tree $T$. If $T$ is a single leaf node, then $S(T) = 2^{-0} = 1$. Otherwise, both the left and right subtrees, $T_l$ and $T_r$, satisfy $S(T_l) \le 1$ and $S(T_r) \le 1$ by inductive hypothesis. However, the depth of each leaf node in the tree is one more than the depth of the leaf node in the corresponding child tree. Therefore, $$S(T) = \sum 2^{-d_i} = \sum_{i~\mathrm{for~left~subtree}} 2^{-d_i} + \sum_{i~\mathrm{for~right~subtree}} 2^{-d_i} = \frac{1}{2} (S(T_l) + S(T_r)) \le \frac{1}{2} (1 + 1) = 1.$$ (And in fact, it's easy to see by a very similar proof that for any full binary tree $T$, $S(T) = 1$.)