k-ary Trees Prova de indução - algoritmo, árvore, árvore binária

Eu estou ficando perplexo com este problema:

Você tem uma árvore com cada nó interno tendo k filhos, com k> = 2. Qual é o número máximo de nós que essa árvore pode ter, se sua profundidade for d? Prove seu responder por indução em d.

Então eu percebo que se k fosse 2, a série geométrica seria 1 + 2 + 4 + 8 ... + 2 ^ n, mas eu não consigo entender como incluir profundidade e como prová-la indutivamente.

Respostas:

O número de itens em uma árvore k-ay completa de n níveis é (k^n - 1)/(k - 1).

Uma árvore binária de 5 níveis, por exemplo, possui 31 nós (1 + 2 + 4 + 8 + 16). Ou:

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

Uma árvore 4-ary de 4 níveis tem 85 nós (1 + 4 + 16 + 64)

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

Se você escrever alguns desses para valores diferentes de k, você deve ser capaz de obter a prova indutiva.