# 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.

-

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$.

-
The formula counts sequences of $k$ labeled trees with a total number of $n$ vertices; however, my main interest is in the recurrence relation and whether there is some straightforward way of using it to obtain the result. –  Gadi A May 4 '11 at 18:06