29
$\begingroup$

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)?

Regards

//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

$\endgroup$
15
  • 5
    $\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$
    – AUK1939
    Jan 27, 2011 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$
    – AUK1939
    Jan 27, 2011 at 0:12
  • 11
    $\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$ Jan 27, 2011 at 1:12
  • 13
    $\begingroup$ "This question is unlikely to help any future visitors"? NO, this question helped me a lot. $\endgroup$
    – fairytale
    Jul 6, 2017 at 16:58
  • 4
    $\begingroup$ Wow, this question helped me, how come it's too localized, very very weird!, If it should be closed, change the reason at least! $\endgroup$
    – Rainb
    Jun 29, 2021 at 5:56

2 Answers 2

19
$\begingroup$

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

$\endgroup$
10
  • $\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$ Jan 26, 2011 at 21:17
  • 2
    $\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$
    – AUK1939
    Jan 26, 2011 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$ Jan 26, 2011 at 21:39
  • 3
    $\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$ Jan 26, 2011 at 21:54
  • 3
    $\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$ Jan 8, 2019 at 17:02
24
$\begingroup$

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*}

$\endgroup$
6
  • $\begingroup$ Cheers, again if you could provide a reference I would be grateful... $\endgroup$
    – AUK1939
    Jan 27, 2011 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, 2011 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, 2017 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, 2017 at 14:42
  • $\begingroup$ @Frank: I don't know. $\endgroup$
    – Ira Gessel
    Feb 21, 2017 at 2:16

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