If we have a tree which is similar to a binary tree, but each internal node has exactly 5 nodes (instead of 2), and leaf nodes in deepest layer have no children.
n(d) = total number of nodes at exactly depth d, e.g. so root node depth 0, n(0) = 1.
At root node d = 0, and root is the only node, and so n(0) = 1. At d = 1, n(1) = 2
How could I work out the recurrence formula for n(d), and solve the recurrence relation? Could someone point me in the correct direction please.
by the way, n(d) is only the number of nodes at exactly depth d, and is not ‘the total number of nodes at depth d or less.
HINT: Notice that if $d\ge 1$, then $n(d+1)=5n(d)$, since each of the $n(d)$ nodes at depth $d$ has $5$ children. Thus,
$$\begin{align*} n(1)&=2\\ n(2)&=5\cdot2\\ n(3)&=5(5\cdot2)=5^2\cdot2\\ n(4)&=5(5^2\cdot2)=5^3\cdot2 \end{align*}$$
This gives you the recurrence, and from these data it shouldn’t be too hard to guess a closed form for $n(d)$ (and of course then prove that it’s correct).