prove an inequality on binary tree

Question

Let $\mathcal{T}_n$ be the set of ordered binary trees that have n leaves.

$d_T(v)$ means the node $v$'s depth in the tree T.

Prove: for any $T\in \mathcal{T}_n$ , for any $\{c_1,c_2,...c_n\}$ , $c_i >0$ , $S=\sum_i c_i$

$$ -\sum_{i=1}^n(c_i\cdot\log_2(c_i/S)) \le \sum_{i=1}^{n} (c_i\cdot d_T(v_i)) $$

$v_i$ means the i-th leaf in tree T.

---

My primary thought:

Since it has log2, so maybe 2^x can be a direction. Then 2 leaves have the same parent, their depth are the same. $2^{-depth1} + 2^{-depth} = 2^{-parent's depth}$

Answer 1

Gibbs'inequality implies that $$-\sum _{i=1}^{n}p_{i}\log p_{i}\leq -\sum _{i=1}^{n}p_{i}\log q_{i}$$ if $p_i\ge0$, $q_i\ge0$, $\sum _{i=1}^{n}p_{i}=1$ and $\sum _{i=1}^{n}q_{i}\le1$.

---

Let $T$ be a binary tree with $n$ leaves $v_1, \cdots, v_n$ and $q_i=2^{-d_T(v_i)}$. Let $p_i=c_i/S$. It is obvious that

1. $p_i\ge0$ and $\sum _{i=1}^{n}p_{i}=1$,
2. $q_i\ge0$ and $\sum _{i=1}^{n}q_{i}\le1$,

except that last inequality.

Claim: $\sum_{i=1}^{n} 2^{-d_T(v_i)}\le 1$.
Proof: This is immediate from the recursive nature of a binary tree, as indicated by the thought at the end of the question.

Now we can obtain the inequality at the start of this answer. It is none other than the wanted inequality in the question.