# Double sum factorial manipulation

$$\sum_{B = 0}^{n-1} \sum_{A = 0}^{n-B-1} \frac{(n-1)!}{B!(n-B-1)!} \frac{(n-B-1)!}{A!(n-B-A-1)!} \frac{A}{A+B+1}$$

This is driving me nuts! Is there anyway to reduce

$$\sum_{B = 0}^{n-1} \sum_{A = 0}^{n-B-1} \frac{(n-1)!}{A!B!(n-A-B-1)!} \frac{A}{A+B+1}$$

beyond

$$\sum_{B = 0}^{n-1} \sum_{A = 0}^{n-B-1} \frac{(n-1)!}{(A-1)!B!(n-A-B-1)!} \frac{1}{A+B+1}$$

I can't figure out how to deal with that $$\frac{1}{A+B+1}$$ term in any way that brings it inside the $$\frac{1}{n-A-B-1}$$ term. Is this not possible?

• My first instinct is to rewrite this with binomial coefficients or multinomial coefficients as that may help direct me to certain patterns. $\sum\limits_{B=0}^{n-1}\sum\limits_{A=0}^{n-B-1} \binom{n-1}{B}\binom{n-1-B}{A}\frac{A}{A+B+1}$. So, it looks like we might be in a scenario where there are $n$ total people, one of which is special. We choose $B$ of the non-special people to be in one group and we choose $A$ of the remaining non-special people to be in another group. Further, we range over all possible values of $A,B$. If it weren't for that $\frac{A}{A+B+1}$ it would be $3^{n-1}$ – JMoravitz May 7 at 14:53
• Exactly - this problem actually originates with a multinomial distribution that I'm multiplying by that $\frac{A}{A+B+1}$ term. The denominator $A+B+1$ is killing me though. I can't get it inside the factorial no matter how I try. The binomial case ($A+1$ or $B + 1$ is easy to handle. – dreicht May 7 at 14:59
• Plugging it into Wolframalpha gives a solution in the form of a DifferenceRoot, oddly enough. – InterstellarProbe May 7 at 15:13

We obtain \begin{align*} \color{blue}{\sum_{B=0}^{n-1}}&\color{blue}{\sum_{A=0}^{n-B-1}\binom{n-1}{B}\binom{n-1-B}{A}\frac{A}{A+B+1}}\\ &=\sum_{B=0}^{n-1}\binom{n-1}{B}\sum_{A=1}^{n-1-B}\binom{n-1-B}{A}A\int_{0}^{1}z^{A+B}\,dz\tag{1}\\ &=\int_{0}^{1}\sum_{B=0}^{n-1}\binom{n-1}{B}\sum_{A=1}^{n-1-B}\binom{n-2-B}{A-1}(n-1-B)z^{A+B}\,dz\tag{2}\\ &=\int_{0}^{1}\sum_{B=0}^{n-1}\binom{n-1}{B}(n-1-B)\sum_{A=0}^{n-2-B}\binom{n-2-B}{A}z^{A+B+1}\,dz\tag{3}\\ &=\int_{0}^{1}\sum_{B=0}^{n-1}\binom{n-1}{B}(n-1-B)z^{B+1}(1+z)^{n-2-B}\,dz\tag{4}\\ &=\int_{0}^{1}\sum_{B=0}^{n-1}\binom{n-2}{B}(n-1)z^{B+1}(1+z)^{n-2-B}\,dz\tag{5}\\ &=(n-1)\int_{0}^{1}z\sum_{B=0}^{n-2}\binom{n-2}{B}z^B(1+z)^{n-2-B}\,dz\\ &=(n-1)\int_{0}^{1}z(1+2z)^{n-2}\,dz\tag{6}\\ &=\frac{n-1}{4}\int_{1}^{3}(u-1)u^{n-2}\,du\tag{7}\\ &=\frac{n-1}{4}\int_{1}^{3}\left(u^{n-1}-u^{n-2}\right)\,du\\ &=\frac{n-1}{4}\left.\left(\frac{1}{n}u^n-\frac{1}{n-1}u^{n-1}\right)\right|_{1}^{3}\\ &=\frac{n-1}{4}\left(\frac{3^n-1}{n}-\frac{3^{n-1}-1}{n-1}\right)\\ &\,\,\color{blue}{=\frac{3^{n-1}}{2}-\frac{3^n-1}{4n}} \end{align*}

Comment:

• In (1) we use the integral to get rid of the denominator. We also start the inner sum with $$A=1$$.

• In (2) we use the binomial identity $$\binom{p}{q}=\binom{p-1}{q-1}\frac{p}{q}$$.

• In (3) we shift the index of the inner sum to start with $$A=0$$.

• In (4) we apply the binomial theorem.

• In (5) we use the binomial identity $$\binom{p}{q}=\binom{p-1}{p-q-1}\frac{p}{p-q}$$.

• In (6) we use again the binomial theorem.

• In (7) we substitute $$1+2z=u, 2dz=du$$.

• Just checking, where do you get the $1+2z$ in going from (3) to (4)? Shouldn't it be $1+z$? – Marko Riedel May 8 at 16:22
• @MarkoRiedel: Yes, thanks for pointing at the mistake. – Markus Scheuer May 8 at 16:42
• In the second line of (5) there seems to be a spurious $(n-1).$ – Marko Riedel May 8 at 16:56
• @MarkoRiedel: Thanks again, Marko. – Markus Scheuer May 8 at 17:04
• Can you check (3) to (4)? (Duplicate $n-1-B.$) – Marko Riedel May 8 at 17:07

Wolfram Alpha found this sequence which seems to match the sum for all positive integers...

$$a_n = \frac{3^{n-1}}{2} - \frac{3^n - 1}{4n}$$

• Can I ask how you got this? What did you enter into Wolfram? I'm entering the sums and I don't get this, but it evaluates to the same answer. – dreicht May 7 at 19:51
• @dreicht By calculating the first few values of the sum with $n=1,2,3\dots$, and tried to get Wolfram to identify the sequence... it didn't work, so I tried removing the fractions by multiplying everything by $n$, which did work – Infiaria May 7 at 19:56
• Thank you! Didn't think of trying that. – dreicht May 7 at 20:03