Proof by Induction of the sum of heights of nodes in a full binary tree

Question

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.

Answer 1

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?