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:
N-H-1 become)?