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.


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

| cite | improve this answer | |
  • $\begingroup$ Thank you. Binomial coefficient does not appear in above formula (1) ? $\endgroup$ – david Nov 20 '19 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$ – Iosif Pinelis Nov 20 '19 at 19:27
  • $\begingroup$ Thank you for the explanation. $\endgroup$ – david Nov 20 '19 at 20:14
  • $\begingroup$ @david : I think (1) rather suggests that this problem has actually not much to do with binomial coefficients. $\endgroup$ – Iosif Pinelis Nov 21 '19 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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