Let $f(x)=\sum _{n=0}^{\infty } b_nx^n$ and $\frac{1}{f(x)}=\sum _{n=0}^{\infty } d_nx^n$. Then the coefficients of the reciprocal of $f(x)$ can be written down. The first few terms are:

$d_0 = \frac{1}{b_0}$,

$d_1 = -\frac{b_1}{b_0^2}$,

$d_2 = \frac{b_1^2-b_0 b_2}{b_0^3}$

$d_3 = -\frac{b_1^3-2 b_0 b_1 b_2+b_0^2 b_3}{b_0^4}$


I was wondering if there is a general recursive (preferably not of course) formula for the coefficients of the reciprocal. If an arbitrary $n$ is given, can I write down a formula for $d_n$ (recursive or not)?


//edit: as the comments below suggest I think people are misinterpretating the question. I am not looking for someone to show me how to solve a system of linear equations by substitution... I want a formula for d_n, Since posting the question, I found such a formula for $d_n$ at http://functions.wolfram.com/GeneralIdentities/7/, see the section on Ratios of the direct function ... if anyone knows of how this formula is derived or any other references to it or similar formulas please let me know... thanks

  • 1
    $\begingroup$ There's no $a_n$ in your functions, only $b_n$. And this really, really does look like homework, and is not research level. But anyway, before this gets closed: just use $f(x) \cdot \frac{1}{f(x)} = 1 + 0 \cdot x + 0 \cdot x^2 + \ldots$ and the formulae for multiplication of power series. $\endgroup$ – Zen Harper Jan 26 '11 at 18:59
  • 4
    $\begingroup$ Yuan, how can you close this question on the basis that its a staightforward application of the Faa di Bruno equation ... since 1) this equation is not known by many (read the third line of this paper, romanpress.com/MathArticles/FaaDiBruno.pdf). and 2) Even if the Faa di Bruno equation does provide an answer, its equivalence to the answer posted at functions.wolfram.com/GeneralIdentities/7 is far from trivial ... and finally before you stupidly voted to close this question look at the responses below. The problem may not be hard but certainly not trivial!! $\endgroup$ – mark Jan 27 '11 at 0:11
  • 2
    $\begingroup$ And Willie Wong!! the reference you pointed me to simply suggests you didnt even read or understand the question ... so you foolishly closing the question has annoyed because I was having a good discussion about the solution with other members. $\endgroup$ – mark Jan 27 '11 at 0:12
  • 7
    $\begingroup$ Actually I don't see the need of closing this question, for these reasons: (1) even a simple question may be of interest to other professional mathematicians not in that very field; and (2) sometimes simple or naive questions here gave rise to wonderful answer by our best users. That said, I would recommend aukm not to feel offended, and to avoid quarreling --for some reasons it's considerd umpolite. $\endgroup$ – Pietro Majer Jan 27 '11 at 1:12
  • 5
    $\begingroup$ "This question is unlikely to help any future visitors"? NO, this question helped me a lot. $\endgroup$ – fairytale Jul 6 '17 at 16:58

Assume $b_0=1$ to simplify things. You want a closed formula for the recursively defined sequence $$d_0=1$$ $$d_n=-\sum_{k=0}^{n-1}d_kb_{n-k}. $$ Let $\alpha=(\alpha_1,\dots,\alpha_r)\in \mathbb{N}_ +^\omega$ be a multi-index with length $l(\alpha):=r$ and weight $|\alpha|:=\sum_{j=1}^r\alpha_j$. Let's denote $b_\alpha:=b_{\alpha_1}\dots b_{\alpha_r}$.

We have (induction) $$d_n:=\sum_{|\alpha|=n}(-1)^{l(\alpha)}b_\alpha. $$

There are of course several equal terms in the sum, due to the commutativity; summing equal terms, a corresponding smaller set of indices would be the increasing multi-indices (the number of terms in the sum would then be the number of partitions $p(n)$).

| cite | improve this answer | |
  • $\begingroup$ Or you can derive it just expanding the formal series $(1+y)^{-1}$ with $y:=\sum_{k=1}^\infty b_k x^k$, and reordering. $\endgroup$ – Pietro Majer Jan 26 '11 at 21:17
  • 1
    $\begingroup$ Impressive, and ofcourse for $b_0 \neq 0$ the recursive relationship would be $d_n=\begin{cases} \frac{1}{b_0} & n=0 \\ -\sum _{k=0}^{n-1} \frac{d_k}{b_0}b_{n-k} & n\geq 1 \end{cases}$ Can you point me to any references. I am not familiar with multi indices, but will look into them to see how this recursive relation is solved. Also by any chance have you got any good references to solution techniques (like this one) to recurrence relations. This is a type of math I have never learnt, but it is catching my interest more and more. $\endgroup$ – mark Jan 26 '11 at 21:30
  • $\begingroup$ While far from being related to the actual problem, the discussion reminds me the following: (a) exact formula $$ det(A)=\sum_{\sigma \in S_n} \epsilon({\sigma}) {a_{1}}^{\sigma(1)} \cdots {a_{n}}^{\sigma(n)} $$ compared with (b) recursive formula: expansion by the first line of the determinant. Difficult to say if (a) or (b) can give a closed formula for say the determinant of a Hilbert matrix. $\endgroup$ – Luis H Gallardo Jan 26 '11 at 21:39
  • 2
    $\begingroup$ @aukm. Well, usually one treates recursive equations for sequences translating them into equations for the generating functions, because power series have a rich algebraic and analytic structure. For these techiques, you may like (some chapters of) Knuth's Concrete mathematics, or Wilf's Generating functionology. More advanced books, Enumerative Combinatorics by Stanley, and Analytic Combinatorics by Flajolet. $\endgroup$ – Pietro Majer Jan 26 '11 at 21:54
  • 2
    $\begingroup$ (Incidentally, (7 years later) I see I forgot one author in a reference I gave above: Analytic Combinatorics by Flajolet and Sedgewick. My inexcusable excuses!) $\endgroup$ – Pietro Majer Jan 8 '19 at 17:02

Without loss of generality we can take $b_0$ to be 1, since \begin{equation*}\sum_{n=0}^\infty b_n x^n = b_0\biggl( 1+\sum_{n=1}^\infty (b_n/b_0)x^n\biggr). \end{equation*} Then for $b_0=1$ we have \begin{equation*} \frac1{f(x)} = \biggl( 1+\sum_{n=1}^\infty b_n x^n\biggr)^{-1}\\ =\sum_{m=0}^\infty (-1)^m\biggl( \sum_{n=1}^\infty b_n x^n\biggr)^m. \end{equation*} Expanding by the multinomial theorem and extracting the coefficient of $x^n$ gives \begin{equation*} \frac1{f(x)} = \sum_{n=0}^\infty \kern 3pt x^n \kern -5pt \sum_{m_1+2m_2+3m_3+\cdots = n} (-1)^{m_1+m_2+\cdots} \binom{m_1+m_2+\cdots}{m_1, m_2, \ldots} b_1^{m_1} b_2^{m_2}\cdots.\end{equation*}

| cite | improve this answer | |
  • $\begingroup$ Cheers, again if you could provide a reference I would be greatful... $\endgroup$ – mark Jan 27 '11 at 1:06
  • 1
    $\begingroup$ If we generalize to $f(x)^r$ then the coefficients in the expansion are called potential polynomials (though they're expressed in terms of exponential generating functions, so the formula will have some additional factorials.) A formula for potential polynomials, which generalizes this formula, can be found in Comtet's Advanced Combinatorics, section 3.5. These polynomials are closely related to Bell polynomials. Another reference is Weiping Wang and Tianming Wang, General identities on Bell polynomials. Comput. Math. Appl. 58 (2009), no. 1, 104–118. $\endgroup$ – Ira Gessel Jan 28 '11 at 16:08
  • $\begingroup$ @IraGessel, I am curious about the Big-0 running time of potential polynomials . How can it be improved to nearly linear running time? Would Hansel Lifting help for this purpose? Thank you. $\endgroup$ – Frank Feb 18 '17 at 11:20
  • $\begingroup$ @Ira Gessel, I am curious about the Big-0 running time of potential polynomials . How can it be improved to nearly linear running time? Would Hansel Lifting help for this purpose? Thank you. $\endgroup$ – Frank Feb 18 '17 at 14:42
  • $\begingroup$ @Frank: I don't know. $\endgroup$ – Ira Gessel Feb 21 '17 at 2:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.