Sum of heights in a complete binary tree (induction)
A complete binary tree of height $h$ has exactly $2^{h-k}$ nodes of height $k$ for $k=0,\ldots,h$, and $n=2^0+\cdots+2^h = 2^{h+1}-1$ nodes in total. The total sum of heights is thus
$$
\sum_{k=0}^h 2^{h-k}k = 2^h \sum_{k=0}^h \frac{k}{2^k} = 2^h \left(2 - \frac{h+2}{2^h}\right) = 2^{h+1} - (h+2) = n - \log_2 (n+1).
$$



The answer below refers to full binary trees.

I'm assuming the following definition of height. The height of a tree is the length of the longest root-to-leaf path. The height of a vertex in a tree is the height of the subtree rooted at this vertex. Denote the height of a tree $T$ by $h(T)$ and the sum of all heights by $S(T)$.

Here are two proofs for the lower bound. The first proof is by induction on $n$. We prove that for all $n \geq 3$, the sum of heights is at least $n/3$. The base case is clear since there is only one complete binary tree on $3$ vertices, and the sum of heights is $1$. Now take a tree $T$ with $n$ leaves, and consider the two subtrees $T_1,T_2$ rooted at the children of the root, containing $n_1,n_2$ vertices, respectively. Suppose first that $n_1,n_2 \geq 3$. Then
$$
S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + n_1/3 + n_2/3 = n/3 + 2/3 &gt; n/3.
$$
If (say) $n_2 = 1$ then
$$
S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + (n-2)/3 = n/3 + 1/3 &gt; n/3.
$$
This completes the proof.

The second proof proceeds by bounding the number of leaves in a complete binary tree. Order the children of every node so that it has a left child and a right child. Exactly half of the leaves are left children. Each left child has a different parent, and in particular each left leaf has a different parent. So a tree $T$ with $f$ leaves has at least $f/2$ non-leaves. In particular, the total number of vertices $n$ satisfies $n \geq f + f/2 = (3/2)f$, so that $(2/3)n \geq f$ and so $n-f \geq n/3$. We conclude that
$S(T) \geq n-f \geq n/3$.

The upper bound can be proved along the lines of the second proof. Suppose that there are $f$ leaves. Thus there are at most $f/2$ vertices at height $1$, at most $f/4$ vertices at height $2$, and generally speaking, at most $f/2^h$ vertices at height $h$. Therefore the total height of vertices is at most
$$
\sum_{h=0}^\infty h \frac{f}{2^h} = f \sum_{h=0}^\infty \frac{h}{2^h} = 2f \leq 2n.
$$