Cantidad de nodos en un árbol

Sea un árbol n-ario completo de altura h.

En el nivel 0 tendrá un solo nodo: la raíz. En el segundo tendrá $n$ nodos, en el tercero $n^{2}$ ; en general, en el nivel h tendrá $n^{h}$ nodos.

Para saber la cantidad total C de nodos que tiene el árbol completo de altura h, tendremos que sumar la cantidad de nodos de cada uno de los niveles:

$C=\sum _{k=0}^{h}n^{k}$

Simplificando la expresión

$C=\sum _{k=0}^{h}n^{k}=n^{0}+n^{1}+n^{2}+\cdots +n^{h-1}+n^{h}$

Multiplicando ambos lados por n:

$n.C=n^{1}+n^{2}+\cdots +n^{h-1}+n^{h}+n^{h+1}$

Restando miembro a miembro:

$n.C-C=n^{1}+n^{2}+\cdots +n^{h-1}+n^{h}+n^{h+1}-(n^{0}+n^{1}+n^{2}+\cdots +n^{h-1}+n^{h})$

$n.C-C=-n^{0}+n^{h+1}$

$(n-1).C=n^{h+1}-1$

$C={\cfrac {n^{h+1}-1}{n-1}}$