I am trying to show that $\sum_{i=1}^{M} 2^{-di} \leq 1 $ for a Binary Tree with $M$ leaves each with a depth of $d_i$.
I understand intuitively why this is the case, as every subtree at level d, can at most contribute $2^{-di}$ to the above sum, which, would mean that the left and right children of a root node could add at most only 1/2 to the above sum, and therefore no tree of any construction, if a binary tree, could exceed one.
That is not a rigorous mathematical proof, however. To make it formal, I tried to perform simple induction on a binary tree to prove that the inequality holds for any number of leaves $M$.
We start first with a lemma that may prove very useful as we proceed:
Lemma
We want to show that if each node of Binary tree is full $\implies \sum_{n=1}^{M} 2^{-di} =1 $ . We prove this by induction. Let us start with $M = 1$. There are two categories of Binary Trees we can construct that meet this condition. One is a root node with no children. This tree satisfies the condition of being full. It also satisfies the formula $\sum_{n=1}^{M} 2^{-di} =1 $ as $\sum_{n=1}^{1} 2^{-0} = 2^{-0} = 1 $.
The other category is a Binary Tree with a root and left child that is either a leaf or a tree which is a stick of arbitrary length. Both scenarios do not meet the condition of being full. In the first case, if we look at the sum of the tree we Have a leaf of depth 1 which gives us $\sum_{n=1}^{1} 2^{-1} =1/2 $. The second case results , assuming that the leaf is of of depth $dj$ such that $dj > 1$ it follows that the above sum can be no greater than 1/2. Therefore we meet the conditions of fullness implying our formula being equivalent to 1 for these cases.
Our inductive hypothesis, we assume for A Binary Tree of $N$ leaves that if each node is full $ \implies \sum_{n=1}^{N} 2^{-di} =1 $
Then we want to show that for a binary tree of $N+1$ leaves if each Node is full $\implies \sum_{n=1}^{N+1} 2^{-di} =1 $. If we add a leaf to a full tree of N leaves then the resulting tree must turn some leaf $j$ into a parent. This makes the resulting not full as node $j$ has one child. It will also add to the former trees sum of $\sum_{n=1}^{N} 2^{-di}$, which was one, to be equivalent to $1 - 2^{-d_j+1}$. If we make node $j$ full by adding an additional leaf as its child, then the total sum in our formula would be $\sum_{n=1}^{N+2} 2^{-d_i} = 1 - 2^{-d_j} + ( 2^{-d_j+1} + 2^{-d_j+1} )$ = 1. Therefore we show via induction, that if the binary tree is full, $\implies \sum_{n=1}^{M} 2^{-d_i} = 1$ where $M$ is the number of leaves.
Proof
The base case is straightforward, For a tree of $M = 1$ leaves (a root without children), it follows that :
$\sum_{n=1}^{1} 2^{-di} = 2^{-0}=1$
$\implies \sum_{n=1}^{1} 2^{-di} = 2^{-0} \leq 1$
Inductive Hypothesis: Assume that for a binary tree of $M=N$ leaves, that $\sum_{n=1}^{N} 2^{-di} \leq 1 $. Now show that $N+1$ leaves, the original proposition holds.
Case 1: We add a full tree (pretty easy, we replace a leaf j, make it a parent to our new N+ 1 leaf which has a smaller sum than the original leaf therefore it must hold to $\leq 1$
Case 2: We add to a non full tree. If the new node is added to a non-full node, then the addition makes the node full. If it is the only un-full tree in the Binary tree, being full implies from our Lemma that $\sum_{n=1}^{N+1} 2^{-di} = 1 $. How can we show that in this scenario, the $\sum_{n=1}^{N+1} 2^{-d_i} \leq 1$? If there are more un-full nodes, and we fill the node we are adding a leaf to at level $j+1$, then we add only $2^{-d_j}$ to the sum. By our Inductive Hypothesis, we guarantee that before our addition the sum is $\leq 1$.
- This is the missing gap, how do I show that the addition of $2^{-d_j}$ can never be more than 1 if the I.H. holds?