k-ary Дървета Индукция Доказателство - алгоритъм, дърво, двоично дърво

Ще се справям с този проблем:

Имате дърво с всеки вътрешен възел с k деца, с k> = 2. Какъв е максималният брой възли, които такова дърво може да има, ако дълбочината му е d? Докажете своя отговор чрез индукция на d.

Така че осъзнавам, че ако k е 2, геометричната серия ще бъде 1 + 2 + 4 + 8 ... + 2 ^ n, но не мога да разбера как да включа дълбочината и как да я докажа индуктивно.

Отговори:

Броят на елементите в пълно k-arry на n нива е (k^n - 1)/(k - 1).

Двойно дърво от 5 нива, например, има 31 възли (1 + 2 + 4 + 8 + 16). Или:

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

4-аройно дърво от 4 нива има 85 възли (1 + 4 + 16 + 64)

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

Ако напишете няколко от тях за различни ценности k, трябва да можете да извлечете индуктивно доказателство.