k-ary木の誘導証明 - アルゴリズム、ツリー、バイナリツリー

私はこの問題に困惑しています。

k> = 2のk個の子を持つすべての内部ノードを持つツリーがあります。 深さがdの場合、そのようなツリーが持つことができるノードの最大数はいくらですか？証明する dの誘導による答え。

だから、もしkが2なら、幾何級数は1 + 2 + 4 + 8 + 2 ^ nとなるだろうが、深さを含める方法とそれを誘導的に証明する方法を理解することはできない。

回答：

nレベルの完全なk-aryツリー内のアイテムの数は、 (k^n - 1)/(k - 1).

たとえば、5つのレベルのバイナリツリーには31ノード（1 + 2 + 4 + 8 + 16）があります。または：

(2^5 - 1)/(2 - 1) = 31/1 = 31

4レベルの4-aryツリーは85ノード（1 + 4 + 16 + 64）を持ち、

(4^4 - 1)/(4 - 1) = 256/3 = 85

異なる値のもののうちのいくつかを書き出すと k帰納的証明を導くことができるはずです。