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



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.

  • $\begingroup$ 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. $\endgroup$ – Rus May May 5 '16 at 14:30
  • $\begingroup$ 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.... $\endgroup$ – 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.


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

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

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.