Доказательство индукцией суммы высот узлов в полном бинарном дереве

Question

Я пытаюсь доказать следующее по индукции:

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

это проблема для класса алгоритмов.Я думал, что мог бы сделать то, что я обычно делаю для суммирования, то есть предположить, что он работает для некоторого P (m), а затем увеличить сумму для P (m + 1) и работать в обратном порядке, добавляя к правой стороне дополнительныеСуммирование на левой стороне приводит к.

Но эта проблема другая, потому что замена H + 1 меняет каждый член внутри суммирования ... поэтому я не думаю, что техника будет работать.

Это домашняя проблема ... так что я, очевидно, не ожидаю полного решения.Но я не совсем уверен, где взять суммирование, поэтому я ищу другие способы выполнения индукции.

Answer 1

Предполагая, что дерево полно, вы все же можете сделать несколько традиционных доказательств по индукции.Просто напишите, что если это работает для некоторой высоты H, то вы знаете, что сумма высот равна N-H-1 для этой высоты;тогда попробуйте это для высоты H+1.Рассмотрим:

• Какова новая сумма всех узлов в старом дереве (т. Е. Чем становится N-H-1)?
• Какие высоты добавляются в новом уровне узловполное дерево?