# Reference for Coefficient Extraction of Multiple Sum

In a post here, the final answer is obtained by coefficent extraction of the quadruple sum.

$$=n![x^n]\left(\sum_{r=0}^{n}\sum_{k=0}^{r}\sum_{h=0}^{\infty}\sum_{m=0}^{\infty}\binom{r}{k}(-1)^{k+m}\left(\frac{1}{2^r}\right)\frac{(2k+1)^{h}}{h!}\binom{r+m}{m}x^{h+m}\right)$$

$$=n!\sum_{r=0}^{n}\sum_{k=0}^{r}\sum_{m=0}^{n}\binom{r}{k}\binom{r+m}{m}(-1)^{k+m}\left(\frac{1}{2^r}\right)\frac{(2k+1)^{n-m}}{(n-m)!}$$

it would seem that letting $n=h+m$, helped in the extraction by rewriting all $h$ terms as $n-m$. Ultimately I understand how it works, but I am looking for a paper or book that explains this type of move of coefficient extraction with multiple summations. I checked Wilf's Generatingfunctionology and didn't find what I was looking for, and I've seen some texts explain the coefficient extraction process and I understand that, but i just need a book or paper with this type of coefficient extraction.

• The well known text Concrete Mathematics by Graham, Knuth and Patashnik has a section on generating functions (it's section 5.4 in the second edition). They have several examples along the lines you seem to be asking. – Rus May May 5 '16 at 14:30
• This sounds good. I just check my university library and they have it in stock so I will get in on Monday and see what I can find. I should have kept Knuth in mind.... – Eleven-Eleven May 6 '16 at 13:23

Note: We can iteratively move the coefficient of operator $[x^n]$ through each of the sums by respecting powers of $x$ whenever we met them.

We obtain this way \begin{align*} \color{blue}{n![x^n]}&\color{blue}{\left(\sum_{r=0}^{n}\sum_{k=0}^{r}\sum_{h=0}^{\infty}\sum_{m=0}^{\infty}\binom{r}{k}(-1)^{k+m}\left(\frac{1}{2^r}\right)\frac{(2k+1)^{h}}{h!}\binom{r+m}{m}x^{h+m}\right)}\\ &=n![x^n]\left(\sum_{r=0}^{n}\sum_{k=0}^{r}\sum_{m=0}^{\infty}x^m\sum_{h=0}^{\infty}\binom{r}{k}(-1)^{k+m}\left(\frac{1}{2^r}\right)\frac{(2k+1)^{h}}{h!}\binom{r+m}{m}x^{h}\right)\tag{1}\\ &=n!\sum_{r=0}^{n}\sum_{k=0}^{r}\sum_{m=0}^{n}[x^{n-m}]\left(\sum_{h=0}^{\infty}\binom{r}{k}(-1)^{k+m}\left(\frac{1}{2^r}\right)\frac{(2k+1)^{h}}{h!}\binom{r+m}{m}x^{h}\right)\tag{2}\\ &\color{blue}{=n!\sum_{r=0}^{n}\sum_{k=0}^{r}\sum_{m=0}^{n}\binom{r}{k}\binom{r+m}{m}(-1)^{k+m}\left(\frac{1}{2^r}\right)\frac{(2k+1)^{n-m}}{(n-m)!}}\tag{3}\\ \end{align*} in accordance with the claim.

Comment:

• In (1) we exchange the inners sums and factor out $x^m$ from the innermost sum as preparation for the next step.

• In (2) we use the linearity of the coefficient of operator and apply the rule \begin{align*} [x^{p-q}]A(x)=[x^p]x^qA(x) \end{align*} We also set the upper limit of sum with index $m$ to $n$ since the exponent of $x^{n-m}$ is non-negative.

• In (3) we select the coeffcient of $x^{n-m}$.

• @Eleven-Eleven: Many thanks for accepting all the answers. – Markus Scheuer Apr 7 '18 at 6:14