# Proof by Induction of the sum of heights of nodes in a full binary tree – Education Career Blog

I’m trying to prove the following by induction:

``````sum(k*2^(H-k), k = 0 .. H) = N-H-1
``````

it’s a problem for an algorithms class. I was thinking I could do what I normally do for summations, which is to assume that it works for some P(m) and then increment the sum for P(m+1) and work backwards by adding to the right side what the additional summation on the left side produces.

But, this problem is different because substituting H+1 changes each term inside of the summation… so I don’t think that technique will work.

This is a homework problem… so I’m obviously not expecting a complete solution. But, I’m not really sure where to take the summation so I’m looking for other ways of doing the induction.

,

Assuming the tree is full, you can still do a somewhat traditional proof by induction. Just write that if it works for some height `H`, then you know the sum of heights is `N-H-1` for that height; then try it for height `H+1`. Consider:

• What’s the new sum of all the nodes in the old tree (i.e. what does `N-H-1` become)?
• What heights are added with the new level of nodes in the full tree?