Solving (and proving) a combinatorial functional recursive equation I have a sequence of functions $f_k(n)$ defined as follows:
$f_1(n)=n^{n-2}$
$f_k(n)=\sum_{i=1}^{n-1}f_{k-1}(i)\cdot(n-i)^{n-i-2}\cdot{n-k \choose n-i-1}$
My goal is to find and prove a closed-form formula for this sequence (i.e. a formula for $f_k(n)$ which does not depend on $f_{k-1}$).
Actually, I already know (from another source) that the solution is $f_k(n)=n^{n-k-1}k$. However, I still want to know if there is a good method for finding the solution from the equation itself, and most importantly, I want to prove that the closed-form formula is correct.
 A: The way to go for a purely calculatory proof from the recurrence is exponential generating functions.
$$f_1(n)=n^{n-2}$$
$$f_k(n)=\sum_{i=1}^{n-1}f_{k-1}(i)\cdot(n-i)^{n-i-2}\cdot{n-k \choose n-i-1}$$
Define $T_k(z)=\sum_{n=k}^{\infty}\frac{f_k(n)}{(n-k)!}z^{n-k}$.
Note that $T_1(z)=\sum_{n=1}^{\infty}\frac{n^{n-2}}{(n-1)!}z^{n-1}=\frac 1z \sum_{n=1}^{\infty}\frac{n^{n-1}}{n!}z^n=T(z)/z$ where $T$ is the tree function with property $T(z)=z\exp(T(z))$.
We have
$$\frac{f_k(n)}{(n-k)!}z^{n-k}=\sum_{i=1}^{n-1}\frac{f_{k-1}(i)}{(i-(k-1))!}z^{i-(k-1)}\cdot\frac{(n-i)^{n-i-2}}{(n-i-1)!}z^{n-i-1}$$
Sum this relation for $n\ge k$.
$$ T_k(z)=T_{k-1}(z) T_1(z) $$
Therefore, $T_k(z)=T_1(z)^k=T(z)^k/z^k$ and $f_k(n)/(n-k)!$ is the coefficient of $z^{n-k}$ in $T_k$ and thus the coefficient of $z^n$ in $T^k$.
But there is a version of the Lagrange inversion formula that, starting from $T=z \exp T$ gives a formula for the coefficient of $z^n$ in $T^k$.
If $f(T(z))=z$ then this coefficient is:
$$\frac kn \langle z^{-k}\rangle f^{-n}(z) =\frac kn \langle z^{-k}\rangle z^n e^{nz} =\frac kn \langle z^{n-k}\rangle e^{nz} =\frac kn  n^{n-k}/(n-k)!  $$
Therefore, $f_k(n)=n^{n-k-1}k$.
