# Induction on Binary Trees

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?
• Are you sure you are being asked to prove it by induction? Notice that since $M \le 2^d$, $\sum_1^M 2^{-d}= M(0.5^d)\le 2^d(0.5^d)=1$. Also, not sure what the i in $d_i$ means. – user137481 Feb 17 '16 at 20:50
• @user137481 I was not asked a particular proof technique. I was clearly overcomplicating it! Thank you! – Thalatta Feb 18 '16 at 1:40
• How is it that the Number of leaves $M$ is less than $2^{d}$ where $d$ is the depth of a given leaf? (That is what $d_i$ is ) – Thalatta Feb 18 '16 at 1:44
• @user137481 see updated question, I miswrote the original sum of the prompt. – Thalatta Feb 18 '16 at 1:48
• A binary tree of depth 0 has only $2^0$ leaf node as you stated. A binary tree of depth 1 has max $2^1$ leaf nodes. A binary tree of depth 2 has max $2^2$ leaf nodes. Can you see the pattern now? – user137481 Feb 18 '16 at 2:09