Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello

If $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 reprical of f 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 was a general recursive (prefferably not ofcourse) formula for the coefficients of the reciprocal fuction?? That is given an arbitrary $n$, 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

share|improve this question

closed as too localized by Willie Wong, Gjergji Zaimi, Andres Caicedo, Qiaochu Yuan, Gerry Myerson Jan 26 '11 at 22:04

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
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. –  Zen Harper Jan 26 '11 at 18:59
    
    
A homework question?? I dont think you read the question properly, or I lack your higher intellect. its one thing to solve a system on equations its quite another to write down a formula for the solution of the nth variable, n being arbitrary. I found the solution at functions.wolfram.com/GeneralIdentities/7 ... I wonder how it was derived... Possibly somebody smart expanded enough terms found a pattern and used induction. That pattern is quite encryptic though. Any refs found would be appreciated. –  aukm Jan 26 '11 at 19:31
1  
This is a straightforward application of Faa di Bruno (en.wikipedia.org/wiki/Fa%C3%A0_di_Bruno's_formula). Voting to close. –  Qiaochu Yuan Jan 26 '11 at 21:26
4  
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. –  Pietro Majer Jan 27 '11 at 1:12

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
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. –  Pietro Majer Jan 26 '11 at 21:17
    
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. –  aukm Jan 26 '11 at 21:30
    
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. –  Luis H Gallardo Jan 26 '11 at 21:39
2  
@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. –  Pietro Majer Jan 26 '11 at 21:54

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

share|improve this answer
    
Cheers, again if you could provide a reference I would be greatful... –  aukm Jan 27 '11 at 1:06
1  
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. –  Ira Gessel Jan 28 '11 at 16:08
    
If the solution is couched in terms of Taylor series or e.g.f.s rather than power series, interesting connections to permutohedra/permutahedra are obtained. See A133314 and A049019 at oeis.org for formulas analogous to those above as well as connections to matrix inversion of special matrices, a lowering operator, wedge products, and weighted surjections. – Tom Copeland 0 secs ago –  Tom Copeland Oct 19 '11 at 12:51

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