General way to count the number of paths in an out-tree?

The parent node is level $0$. Define level $1$ as the $n$ child nodes below level $0$. Let $k$ be the number of levels. The $k$th level introduces $n^k$ nodes. From each node at level $j$, if $j+p \leq k$, there are $n^p$ paths of length $p$; otherwise no such paths exist as there are not enough levels below. The total number of paths of length $p$ from the $j$th level is $n^jn^p = n^{j+p}$.

Define $f(n, k)$ as number of paths up to level $k$. The formula is

$$f(n, k)=\sum_{j=0}^{k-1}\sum_{p=1}^{k-j}n^{j+p} = \sum_{j + p \leq k} n^{j+p}$$

$f(n, 1) = n$

$f(n, 2) = 2n^2 + n$

$f(n, 3) = 3n^3 + 2n^2 + n$. Note that $f(2, 3) = 34$. An alternative view of the formula is there are $k$ ways to write $k$ as sum of $j + p$, where $j \in \{0, 1 \dots k - 1\}, p \in \{1, 2 \dots, k\}$. Similarly for each $p \leq k$ there are $p$ such ways.

The formula can be thus rewritten as $\displaystyle \sum_{p=1}^k{pn^p}$. According to Wolfram Alpha,

$$f(n,k) = \frac{n(k n^{k + 1} - (k + 1) n^k + 1)}{(n-1)^2}$$