4
$\begingroup$

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

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

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

Thank you.

$\endgroup$
2
  • 2
    $\begingroup$ Being off by an index it is the binomial transform. $\endgroup$
    – Phicar
    Nov 16, 2019 at 14:26
  • $\begingroup$ @Phicar, can you explain a bit more on your comment ? I could not see why original relation is a binomial transform. $\endgroup$
    – david
    Nov 22, 2019 at 5:44

1 Answer 1

4
+50
$\begingroup$

This is an approach of just what i meant in the comments.

Suppose $$A(z)=\sum _{i = 0}^{\infty}x_i\frac{z^i}{i!},$$ and $$B(z)=\sum _{j=1}^{\infty}jy_j\frac{z^j}{j!}$$ then $$A(z)B(z)=\sum _{n =0 }^{\infty}\frac{z^n}{n!}\left (\sum _{i =0}^{n-1}\binom{n}{i}x_i(n-i)y_{n-i}\right )=\sum _{n =0 }^{\infty}\frac{z^n}{(n-1)!}\left (\sum _{i =0}^{n-1}\binom{n-1}{i}x_i(n-i)\frac{y_{n-i}}{n-i}\right )=z\sum _{n =1 }^{\infty}\frac{z^{n-1}}{(n-1)!}\left (\sum _{i =0}^{n-1}\binom{n-1}{i}x_iy_{n-i}\right )=z\sum _{n =1 }^{\infty}\frac{z^{n-1}}{(n-1)!}x_n=zA'(z)$$ From there we get that $$B(z)=\frac{zA'(z)}{A(z)}$$ and so $$y_n=\frac{[z^{n-1}]ln(A(z))'}{n}.$$

$\endgroup$
6
  • $\begingroup$ thank you for the explanation. Is this some kind of binomial transform ? IDo we need do some conversion to interpret such relation as a binomial transform ? $\endgroup$
    – david
    Nov 22, 2019 at 18:11
  • $\begingroup$ Yes, binomial transform is just multiplying by exponential in the exponential generating function. If you know your sequence $x_i$ perhaps you can express formally its exponential function and compose. Perhaps you will find interesting the book "Combinatorial Species and Tree-like Structures". Usually logarithm corresponds to understand your sequence as parts of a finer sequence. Take a look, for example, to Stirling numbers of the first kind. $\endgroup$
    – Phicar
    Nov 22, 2019 at 19:46
  • $\begingroup$ Thank you again. In your previous comments, you wrote: "If you know your sequence xi perhaps you can express formally its exponential function and compose." What do you mean "compose" ? I took a look of Stirling numbers of the first kind on Wiki, what do you mean "Usually logarithm corresponds to understand your sequence as parts of a finer sequence" ? Is your comment related to en.wikipedia.org/wiki/… ? $\endgroup$
    – david
    Nov 22, 2019 at 22:37
  • $\begingroup$ I meant compose it with logarithm. I meant that in the context of Species, the exponential is sequences without order. So logarithm is the inverse of that operation. For the stirling numbers i meant that check that the generating function is a logarithm, that is because permutations are factor into disjoint cycles. So, in some way, factorization of sequences and logarithm is connected(in the theory of species.) $\endgroup$
    – Phicar
    Nov 22, 2019 at 23:32
  • $\begingroup$ It is still not clear to me, do $x_{n}, y_{n} $ or $x_{n}/n! , y_{n+1}/n!$ in the expression ${\displaystyle {x_{n}=\sum _{i = 0}^{n - 1}{\binom {n - 1}{i}}x_{i}y_{n -i} }}.$ form a binomial transform pair ? $\endgroup$
    – david
    Nov 23, 2019 at 1:18

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.