In following, $x_{n}$ is a set of given numbers, n = 0, 1, 2, ...,
$y_{n}$ is defined by the following recursive relation of $x_{n}$:

For example:

${\displaystyle {x_{1}=x_{0}y_{1} }}.$

${\displaystyle {x_{2}={\binom {1}{0}}x_{0}y_{2} + {\binom {1}{1}}x_{1}y_{1} }}.$

${\displaystyle {x_{3}={\binom {2}{0}}x_{0}y_{3} + {\binom {2}{1}}x_{1}y_{2} + {\binom {2}{2}}x_{2}y_{1} }}.$

For simplicity, we can assume $x_{0} = 1$.

Q1: Is there an explicit solution of $y_{n}$ in term of $x_{n}$ ?

Q2: I assume that above relation should be well known, is it a name for such relation ?

Thank you.


1 Answer 1


Concerning Q1, under natural general conditions we can express the exponential generating function of $(y_{j+1})_{j=0}^\infty$ in terms of the exponential generating function of $(x_i)_{i=0}^\infty$.

Indeed, let $$u_i:=\frac{x_i}{i!},\quad v_i:=\frac{y_{i+1}}{i!} $$ for $i=0,1,\dots$. Then $$(m+1)u_{m+1}=\sum_{i=0}^m u_i v_{m-i} \tag{1} $$ for $m=0,1,\dots$. So, if e.g. $|v_i|\le C^i$ for some real $C\ge1$ and all $i$, then, by induction, $|u_i|\le C^i$ for all $i$. Hence, we can define the exponential generating functions $U$ and $V$ of $(y_{j+1})_{j=0}^\infty$ and $(x_i)_{i=0}^\infty$ by $$U(s):=\sum_{i=0}^\infty u_is^i,\quad V(s):=\sum_{i=0}^\infty v_is^i $$ for all $s$ close enough to $0$. Then (1) can be rewritten as $U'(s)=U(s)V(s)$, so that $$V=U'/U. $$

  • $\begingroup$ Thank you. Binomial coefficient does not appear in above formula (1) ? $\endgroup$
    – david
    Nov 20, 2019 at 19:22
  • $\begingroup$ @david : Indeed, the binomial coefficient does not appear in (1), and that is the key. The factorial factors in the binomial coefficient get absorbed into the $u_i$'s and $v_i$'s. $\endgroup$ Nov 20, 2019 at 19:27
  • $\begingroup$ Thank you for the explanation. $\endgroup$
    – david
    Nov 20, 2019 at 20:14
  • $\begingroup$ @david : I think (1) rather suggests that this problem has actually not much to do with binomial coefficients. $\endgroup$ Nov 21, 2019 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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