Binomial expansion (sort of ) rearrangement

Question

Let $$ x_n=\sum_{i=1}^n\binom{n}{i}y_iz_{n-i} \qquad n=1,\ldots,k $$ For general $k$, can you find an explicit expression for $y_k$ only in terms of $x_1,\ldots,x_k$ and $z_1,\ldots,z_k$?

For example, if $k=3$, then \begin{align*} x_3 &=y_3+3y_2z_1+3y_1z_2+z_3 \\ x_2 &=y_2+2y_1z_1+z_2 \\ x_1 &=y_1+z_1 \end{align*} So \begin{align*} y_3&=x_3-3y_2z_1-3y_1z_2-z_3 =x_3-3(x_2-2y_1z_1-z_2)z_1-3(x_1-z_1)z_2-z_3 \\ &=x_3-3(x_2-2(x_1-z_1)z_1-z_2)z_1-3(x_1-z_1)z_2-z_3 \\ &=x_3-3x_2z_1+6x_1z_1^2-6z_1^3-3x_1z_2+6z_1z_2-z_3 \\ \end{align*} For general $k$, I have tried to recursively substitute in and get a very complicated expression.

Can anyone help me find a general (preferably simple) formula for $y_k$? Thanks.

Edit: Here's my lengthy (I think correct) solution: \begin{align*} & y_k=x_{k}-\sum_{k_{1}=2}^{3}\binom{k}{k-k_{1}}z _{k_{1}}x_{k-k_{1}} -\sum_{k_{1}=4}^{5}\binom{k}{k-k_{1}}\left( z _{k_{1}}-\sum_{k_{2}=2}^{k_{1}-2}\binom{k_{1}}{k_{2}}z _{k_{1}-k_{2}}z _{k_{2}}\right) x_{k-k_{1}} \\ & -\sum_{k_{1}=6}^{7}\binom{k}{k-k_{1}}\left( z _{k_{1}}-\sum_{k_{2}=2}^{k_{1}-2}\binom{k_{1}}{k_{2}}z _{k_{1}-k_{2}}z _{k_{2}}+\sum_{k_{2}=4}^{k_{1}-2}\binom{k_{1}}{k_{2}}z _{k_{1}-k_{2}}\sum_{k_{3}=2}^{k_{2}-2}\binom{k_{2}}{k_{3}}z _{k_{2}-k_{3}}z _{k_{3}}\right) x_{k-k_{1}}-\cdots \\ & -\sum_{k_{1}=2l}^{k}\binom{k}{k-k_{1}}\left( z _{k_{1}}-\sum_{k_{2}=2}^{k_{1}-2}\binom{k_{1}}{k_{2}}z _{k_{1}-k_{2}}z _{k_{2}}+\sum_{k_{2}=4}^{k_{1}-2}\binom{k_{1}}{k_{2}}z _{k_{1}-k_{2}}\sum_{k_{3}=2}^{k_{2}-2}\binom{k_{2}}{k_{3}}z _{k_{2}-k_{3}}z _{k_{3}}-\cdots \right. \\ & \left. +\left( -1\right) ^{l-1}\sum_{k_{2}=2l-2}^{k_{1}-2}\binom{k_{1}}{ k_{2}}z _{k_{1}-k_{2}}\cdots \sum_{k_{l-1}=4}^{k_{l-2}-2}\binom{k_{l-2}}{ k_{l-1}}z _{k_{l-2}-k_{l-1}}\sum_{k_{l}=2}^{k_{l-1}-2}\binom{k_{l-1}}{k_{l} }z _{k_{l-1}-k_{l}}z _{k_{l}}\right) x_{k-k_{1}} \end{align*} I needed to program this in and it wasn't as bad as I first thought.

If someone can find a more elegant expression (or simplification), I would accept it as a solution.

Answer 1

Given a sequence $s=(s_1,s_2,\ldots)$, it is useful to consider the exponential generating function $$ f_s(T):=1+\sum_{n\geq 1}s_n\frac{T^n}{n!}. $$ The relationship between the $x=(x_n)$, $y=(y_n)$, and $z=(z_n)$ can be expressed as $$ f_x(T) =f_y(T)\cdot f_z(T). $$

We want to solve for $y$ in terms of $x$ and $z$, so we write $$ f_y(T)=\frac{f_x(T)}{f_z(T)}. $$ The constant term of $f_z(T)$ is $1$, so we can invert as follows: \begin{align*} \frac{1}{f_z(T)}&=\sum_{k\geq 0}(-1)^k\left(\sum_{n\geq 1}z_n\frac{T^n}{n!}\right)^k\\ &=\sum_{k\geq 0}(-1)^k\sum_{n_1,\ldots,n_k\geq 1}\,z_{n_1}\ldots z_{n_k}\frac{T^{n_1+\ldots+n_k}}{n_1!\ldots n_k!}\\ &=\sum_{m\geq 0}\sum_{k\geq 0}(-1)^k\sum_{\substack{n_1,\ldots,n_k\geq 1\\n_1+\ldots+n_k=m}}z_{n_1}\ldots z_{n_k}\frac{T^m}{n_1!\ldots n_k!}. \end{align*}

Finally, we multiply this by $f_x(T)$ and extract the coefficient of $T^n$ to obtain \begin{align*} y_n&=n!\sum_{i=0}^n \frac{x_{n-i}}{(n-i)!}\sum_{\substack{n_1,\ldots,n_k\geq 1\\n_1+\ldots+n_k=i}}(-1)^kz_{n_1}\ldots z_{n_k}\frac{1}{n_1!\ldots n_k!}\\ &=\sum_{\substack{n_1,\ldots,n_k\geq 1\\b\geq 0\\n_1+\ldots+n_k+b=n}}\hspace{-5mm}(-1)^k \binom{n}{n_1,\ldots,n_k,b}x_b z_{n_1}\ldots z_{n_k}. \end{align*} Here $\binom{n}{n_1,\ldots,n_k,b}$ is a multinomial coefficient, and we adopt the convention (as it looks like you did) that $x_0=1$.