Доказательство по индукции, двоичное дерево высоты n имеет 2 ^ (n + 1) -1 узлов.

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

Сначала покажите, что если n = 1, то есть m узлов, а если n = 2, то есть k узлов. Из этого определите формулу m, k, которая работает, когда n = 1 и 2 (т.е. в вашем случае 2 ^ (n + 1) - 1.

Далее предположим, что та же формула работает для n как произвольного значения. наконец, покажите, что формула работает для высоты (n + 1). то есть n означает n + 1 (приращение на один шаг). Этот последний шаг обычно самый сложный, но при необходимости вы можете использовать результаты для n, 1 и 2.

Идея состоит в том, что вы можете увидеть для n = 1 и 2, что формула работает, когда n увеличивается на 1. Затем, если это верно для n, то, доказывая, что это верно для n + 1, прилежный человек может явно вычислить n = 1, 2, затем 3, 4 и т. д. все до n, а затем до n + 1 с шагом в один шаг.