Combinatoric expression for $V_n$

Question

I just want to know how to prove this passage bellow\begin{align*} G(z)&=\sum_{i=0}^{r-1}U_{i}z^{i}\sum_{n=0}^{\infty} \sum_{k_0+k_1+\dots+k_{r-1}=n}\binom{n}{k_0,k_1,\dots,k_{r-1}}a_0^{k_0}a_1^{k_1} \dots a_{r-1}^{k_{r-1}} z^{{k_0+2k_1+\dots+rk_{r-1}}},\\ \sum_{n=0}^{\infty}V_{n}z^{n} &=\sum_{i=0}^{r-1}U_{i}z^{i}\sum_{n=0}^{\infty}z^n \sum_{k_0+2k_1+\dots+rk_{r-1}=n}\binom{k_0+k_1+\dots+k_{r-1}}{k_0,k_1,\dots,k_{r-1}}a_0^{k_0}a_1^{k_1} \dots a_{r-1}^{k_{r-1}}, \end{align*} where G is generating function for sequence $V_n$.

Answer 1

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Hint: $$ z^{k_{0} + 2k_{1} + \cdots + r\,k_{r - 1}} = \sum_{\ell = 0}^{\infty}z^{\ell} \delta_{\ell,k_{0} + 2k_{1} + \cdots + r\,k_{r - 1}} $$ Now, you can "freely" exchange the $\displaystyle\ell$-sum which "isolate" the term $\displaystyle z^{\ell}$ to the left. \begin{align} \mrm{G}\pars{z} & \equiv \sum_{i = 0}^{r - 1}U_{i}z^{i}\sum_{n = 0}^{\infty} \sum_{k_{0} + \cdots + k_{r-1} = n} {n \choose k_{0},\ldots,k_{r - 1}}a_{0}^{k_0}a_{1}^{k_1}\ldots a_{r - 1}^{k_{r - 1}}\,z^{k_{0} + 2k_{1} + \cdots + rk_{r - 1}} \\[5mm] & = \sum_{i = 0}^{r - 1}U_{i}z^{i}\sum_{n = 0}^{\infty}\ \sum_{\sum_{j = 0}^{r - 1} = n} {n \choose k_{0},\ldots,k_{r - 1}}a_{0}^{k_0}a_{1}^{k_1}\ldots a_{r - 1}^{k_{r - 1}}\,\sum_{m = i}^{\infty}z^{m - i}\, \delta_{m,\sum_{j = 0}^{r - 1}\pars{j + 1}k_{j}} \\[5mm] & = \sum_{i = 0}^{r - 1}U_{i}\sum_{m = i}^{\infty}z^{m}\sum_{n = 0}^{\infty}\ \sum_{\sum_{j = 0}^{r - 1} = n} {n \choose k_{0},\ldots,k_{r - 1}}a_{0}^{k_0}a_{1}^{k_1}\ldots a_{r - 1}^{k_{r - 1}}\,\delta_{m,\sum_{j = 0}^{r - 1}\pars{j + 1}k_{j}} \\[5mm] & = \sum_{i = 0}^{\infty}\bracks{i \leq r - 1}U_{i} \sum_{m = 0}^{\infty}z^{m}\bracks{m \geq i}\sum_{n = 0}^{\infty}\ \sum_{\sum_{j = 0}^{r - 1} = n} {n \choose k_{0},\ldots,k_{r - 1}}a_{0}^{k_0}a_{1}^{k_{1}}\ldots a_{r - 1}^{k_{r - 1}}\,\delta_{m,\sum_{j = 0}^{r - 1}\pars{j + 1}k_{j}} \\[5mm] & = \sum_{m = 0}^{\infty}z^{m}\sum_{i = 0}^{\min\braces{\!m,r - 1\!}}U_{i} \sum_{n = 0}^{\infty}\sum_{\sum_{j = 0}^{r - 1} = n} {n \choose k_{0},\ldots,k_{r - 1}}a_{0}^{k_0}a_{1}^{k_{1}}\ldots a_{r - 1}^{k_{r - 1}}\,\delta_{m,\sum_{j = 0}^{r - 1}\pars{j + 1}k_{j}} = \sum_{n = 0}^{\infty}V_{n}z^{n} \end{align} I already exchanged the $\ds{m\ \mbox{and}\ n}$ indexes $\ds{\pars{~m \leftrightarrow n~}}$ to get closer to the OP proposed expression. Then, \begin{align} V_{n} & \equiv \sum_{i = 0}^{\min\braces{\!n,r - 1\!}}U_{i} \sum_{m = 0}^{\infty}\sum_{\sum_{j = 0}^{r - 1} = m} {m \choose k_{0},\ldots,k_{r - 1}}a_{0}^{k_0}a_{1}^{k_{1}}\ldots a_{r - 1}^{k_{r - 1}}\,\delta_{n,\sum_{j = 0}^{r - 1}\pars{j + 1}k_{j}} \end{align} The inner sum is $\ds{i}$-independent such that \begin{align} &\bbx{V_{n} = \pars{\sum_{i = 0}^{\min\braces{\!n,r - 1\!}}U_{i}}\bracks{% \sum_{m = 0}^{\infty}\sum_{\sum_{j = 0}^{r - 1} = m} {m \choose k_{0},\ldots,k_{r - 1}}a_{0}^{k_0}a_{1}^{k_{1}}\ldots a_{r - 1}^{k_{r - 1}}\,\delta_{n,\sum_{j = 0}^{r - 1}\pars{j + 1}k_{j}}}} \end{align}