The maximum number of nodes in a heap tree of degree d and depth k The maximum number of nodes in a binary tree of depth k is defined by $2^{(k+1)}-1$, but the same rule doesn't appear to work for heap trees of different degrees.
Let's say I have the following tree of degree 3
   1
 / | \
2  3  4

Here the depth of the tree is 1. So according to the formula, it will be $3^{(1+1)}-1=8$. But we have 4 nodes here. I am really struggling to adapt the binary tree formula to trees of other degrees.
Any thoughts?
A complete $d$-ary tree of depth $k$ has $d^\ell$ on level $\ell$ (where $0 \leq \ell \leq k$), so its total number of nodes is
$$
\sum_{\ell=0}^k d^\ell = \frac{d^{k+1}-1}{d-1}.
$$