$$\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}$$


$$\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?

  • $\begingroup$ 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}$ $\endgroup$ – JMoravitz May 7 at 14:53
  • $\begingroup$ 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. $\endgroup$ – dreicht May 7 at 14:59
  • $\begingroup$ Plugging it into Wolframalpha gives a solution in the form of a DifferenceRoot, oddly enough. $\endgroup$ – 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*}


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

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

  • $\begingroup$ 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. $\endgroup$ – dreicht May 7 at 19:51
  • $\begingroup$ @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 $\endgroup$ – Infiaria May 7 at 19:56
  • $\begingroup$ Thank you! Didn't think of trying that. $\endgroup$ – dreicht May 7 at 20:03

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.