Sum of heights in a complete binary tree (induction) I need to prove the following statement using induction on the number of nodes in the tree:

The sum of heights of a complete binary tree is $\theta(n)$.

Note: I've tried proving this using mathematical sums. I did manage to show that the sum of heights (lets call it $sum(n)$) is in fact $sum(n)≤c_1n$ for some $c_1$. But, I couldn't show the lower bound ($sum(n)≥c_2n$ for some $c_2$).

The base case is a complete binary tree, with 3 nodes in the height of 1.

The assumption is that for a complete binary tree $T$ with $n$ nodes $sum\in\theta(n)$

I got stuck when i got to the phase of the step. My intuition is to add to the tree another depth of leaves and to prove for the new tree. 

Can someone explain how to complete this step?
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.
$$