How do I solve this recurrence relation?
$$
\left\{{\begin{aligned} u_0 &= \frac{1}{v_0} \\ u_n &= -\frac{1}{v_0}\sum_{i=0}^{n-1}{n\choose i}u_iv_{n-i} \end{aligned}}\right.
$$
I've got the first couple of terms figured out:
$$
\begin{aligned}
u_1&=\frac{-v_1}{v_0^2} \\
u_2&=\frac{2v_1^2-v_0v_2}{v_0^3} \\
u_3&=\frac{-6v_1^3+6v_0v_1v_2-v_0^2v_3}{v_0^4}\\
u_4&=\frac{24v_1^4-36v_0v_1^2v_2+6v_0^2v_2^2+8v_0^2v_1v_3-v_0^3v_4}{v_0^5}
\end{aligned}
$$
It looks like for $u_n$, the first term on the numerator is always $(n!)v_1^n$, and the rest has to do with interger partition of $n$. The sign of the coefficient is deterimined by the order of $v_0$.
This came from trying to express $\mathrm{d}^nu/{\mathrm{d}x^n}$ with derivatives of $v$ where $u(x)v(x)=1$.
Best Answer
We have the following formal power series identity $$\left(\sum_{n\geqslant 0}u_n\frac{t^n}{n!}\right)\left(\sum_{n\geqslant 0}v_n\frac{t^n}{n!}\right)=1.$$
To get rid of signs, and powers of $v_0$ in denominators, let's put $u_n=a_n/v_0$ and $v_n=-b_n v_0$: $$\left\{\begin{aligned}a_0&=1,\\a_n&=\sum_{k=0}^{n-1}\binom{n}{k}a_k b_{n-k},\end{aligned}\right.\qquad\left(1+\sum_{n>0}a_n\frac{t^n}{n!}\right)\left(1-\sum_{n>0}b_n\frac{t^n}{n!}\right)=1.$$
Now, using operations on formal power series, we deduce $$\sum_{n>0}a_n\frac{t^n}{n!}=\left(1-\sum_{n>0}b_n\frac{t^n}{n!}\right)^{-1}-1=\sum_{m>0}\left(\sum_{n>0}b_n\frac{t^n}{n!}\right)^m \\=\sum_{m>0}\sum_{n_1,\ldots,n_m>0}\prod_{k=1}^m\frac{b_{n_k}t^{n_k}}{n_k!}=\sum_{m>0}\sum_{n_1,\ldots,n_m>0}t^{n_1+\cdots+n_m}\frac{b_{n_1}}{n_1!}\cdots\frac{b_{n_m}}{n_m!}.$$
The question asks us to group the terms by fixed powers of $t$, $b_1$, $b_2$, etc.; that is, given $n>0$ and $k_1,k_2,\ldots,k_n\geqslant 0$ such that $1k_1+2k_2+\cdots+nk_n=n$, we want the coefficient of $t^n b_1^{k_1}b_2^{k_2}\cdots b_n^{k_n}$ in the last expression above.
To get it, we count the number of tuples $(n_1,\ldots,n_m)$ that have $k_1$ $1$'s, $k_2$ $2$'s, ..., $k_n$ $n$'s (so we must have $m=k_1+k_2+\cdots+k_n$). This number is the well-known multinomial coefficient $\frac{(k_1+k_2+\cdots+k_n)!}{k_1!\,\cdot\,k_2!\,\cdots\,k_n!}$: $$a_n=n!\sum_{\substack{k_1,\,k_2,\,\ldots,\,k_n\,\geqslant\,0\\1k_1+2k_2+\cdots+nk_n=n}}\frac{(k_1+k_2+\cdots+k_n)!}{k_1!\,\cdot\,k_2!\,\cdots\,k_n!}\left(\frac{b_1}{1!}\right)^{k_1}\left(\frac{b_2}{2!}\right)^{k_2}\cdots\left(\frac{b_n}{n!}\right)^{k_n}.$$ To get back to $u_n$ and $v_n$, as stated at the beginning, put $b_n=-v_n/v_0$ and take $u_n=a_n/v_0$.
One may recognize a big gun here.