I need to calculate the following summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m-j}\choose{k-j}}}{k\choose j}r^{k-j+i}$$ I do not know if it is a well-known summation or not.

(The special case when $r=1$ is also helpful.)

Even a little simplification is good, unfortunately I cannot simplify it more than this!

Edit: another way to write this summation is: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{k\choose j}}r^{k-j+i}$$ Anybody can help with this one?

  • 1
    $\begingroup$ Why do you need to calculate it? What does it represent? That might throw some light on possible simplifications. $\endgroup$ – Matthew Conroy Jan 7 '14 at 21:36
  • $\begingroup$ It is the final result of the long solution of a problem that I just want to simplify, I don't think the rest of the solution would help. $\endgroup$ – Mah Jan 7 '14 at 22:59
  • $\begingroup$ But what is the problem? $\endgroup$ – Matthew Conroy Jan 7 '14 at 23:00
  • 1
    $\begingroup$ It is the summation of mean first passage time from a state to zero of a birth-and-death process times the asymptotic probability of being in that state. $\endgroup$ – Mah Jan 7 '14 at 23:06

Hint: This is just a starter which might be helpful for further calculation. We obtain a somewhat simpler representation of the triple sum.

\begin{align*} \sum_{j=1}^m&\sum_{i=j}^m\sum_{k=j}^m\frac{\binom{m}{i}\binom{m-j}{k-j}}{\binom{k}{j}}r^{k-j+i}\\ &=\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^{m}\frac{m!}{i!(m-i)!}\cdot\frac{(m-j)!}{(k-j)!(m-k)!}\cdot\frac{j!(k-j)!}{k!}r^{k-j+i}\tag{1}\\ &=\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^{m}\frac{\binom{m}{k}\binom{m}{i}}{\binom{m}{j}}r^{k-j+i}\tag{2}\\ &=\sum_{j=1}^m\frac{1}{\binom{m}{j}r^j}\sum_{i=j}^m\binom{m}{i}r^i\sum_{k=j}^m\binom{m}{k}r^k\tag{3}\\ &=\sum_{j=1}^m\frac{1}{\binom{m}{j}r^j}\left(\sum_{k=j}^m\binom{m}{k}r^k\right)^2 \end{align*}


  • In (1) we write the binomial coefficients using factorials

  • In (2) we cancel out $(k-j)!$ and rearrange the other factorials to binomial coefficients so that each of them depends on one running index only

  • In (3) we can place the binomial coefficients conveniently and see that the sums with index $i$ and $k$ are the same

  • $\begingroup$ I get the feeling that $\sum_{k=j}^m\binom mkr^k$ should be solvable... $\endgroup$ – Simply Beautiful Art Jun 7 '16 at 20:58
  • $\begingroup$ According to wolfram alpha: wolframalpha.com/input/?i=sum+binom(m,k)+r%5Ek $$\sum_{k=j}^m\binom mkr^k=\left(-r^{n+1}\binom m{n+1}[_2F_1(1,-m+n+1;n+2;-r)]+(r+1)^m-1\right)+\left(-r^j\binom mj[_2F_1(1,-m+j;j+1;-r)]+(r+1)^m-1\right)$$$$=r^j\binom mj[_2F_1(1,j-m;j+1;-r)]-r^{n+1}\binom m{n+1}[_2F_1(1,-m+n+1;n+2;-r)]$$where $_2F_1$ is the hypergeometric function. $\endgroup$ – Simply Beautiful Art Jun 7 '16 at 21:13
  • $\begingroup$ @SimpleArt: Thanks a lot for the bounty! :-) Regarding your feeling: I don't think there is a closed form. Recall that $j=0$ gives $(1+r)^m$ and from this expression we subtract $j$ summands of the form $\binom{m}{k}r^k$ which has no closed form in general as far as I know. $\endgroup$ – Markus Scheuer Jun 7 '16 at 21:15
  • $\begingroup$ Haha, take that for a closed form lol. I do think attempting to summate that is hopeless. $\endgroup$ – Simply Beautiful Art Jun 7 '16 at 21:16
  • 1
    $\begingroup$ Sh.... I think its nice too. :-) wolframalpha is awesome. $\endgroup$ – Simply Beautiful Art Jun 7 '16 at 21:21

It appears (by empirical experimentation) that as a polynomial $P_m(r)$ this has the following expansion $$ P_m(r)=\frac{(m-1)!}{m!\,0!}q_1(m)r^{2m-1}+\frac{(m-2)!}{m!\,1!}q_2(m)r^{2m-2}+\frac{(m-3)!}{m!\,2!}q_3(m)r^{2m-3}+\ldots\\=\sum_{k=1}^{2m-1}\frac{(m-k)!}{m!(k-1)!}q_k(m)r^{2m-k}, $$ where $q_k(m)$ are some integer-valued functions, which for can be described by degree-$(2k-2)$ polynomial, i.e. \begin{align} q_1(m)&=1,\\ q_2(m)&=2m^2-2m+2,\\ q_3(m)&=8 m^6-60 m^5+188 m^4-336 m^3+392 m^2-312 m+144,\\ q_4(m)&=16 m^8-208 m^7+1148 m^6-3604 m^5+7292 m^4-10252 m^3+10408 m^2-7392 m+2880,\\ q_5(m)&=32 m^{10}-640 m^9+5560 m^8-27920 m^7+91096 m^6-206360 m^5+339680 m^4-418840 m^3+387312 m^2-250560 m+86400. \end{align}

Note that $(m-k)!$ should be understood as ill-defined for $k>m$ in these formulas, and the corresponding coefficients cannot be computed by the above formulas. I also couldn't find any sufficiently general pattern in these polynomials.

It seems also empirically true that $$ P_m(1)\simeq \frac{4^m}{m}\left(1+\frac{2}{m}+\frac{8}{m^2}+\frac{44}{m^3}+\ldots\right), $$ but I cannot guarantee the numbers in the parenthesis. The next coefficient seems to be $308$ or close to it, which would suggest this sequence.

  • $\begingroup$ You may wish to use $(m-k)!=\Gamma(m-k+1)$, the Gamma function $\endgroup$ – Simply Beautiful Art Jun 1 '16 at 23:25
  • $\begingroup$ @SimpleArt, of course I know that. What I meant is that the Gamma function has poles for integer $k>m$ which are not cancelled in the formulas, so this doesn't help. $\endgroup$ – Peter Kravchuk Jun 2 '16 at 0:11
  • $\begingroup$ Hm, how did you arrive at your $q_n(m)$ formulas? And what is the expansion for $P_m(r)$? Most expansions don't come out like that. $\endgroup$ – Simply Beautiful Art Jun 2 '16 at 0:41
  • $\begingroup$ @SimpleArt, this is the standard guesswork using Mathematica. I do not understand what do you mean by the second part of your question, can you please be more specific? $\endgroup$ – Peter Kravchuk Jun 2 '16 at 3:11
  • $\begingroup$ It is just uncommon for an expansion to take the form $\frac{(m-k)!}{m!(k-1)!}$, obviously because $(m-k)!$ tends to be undefined as you have noticed. I was more or less wondering if there was a "method to your madness" if you will. $\endgroup$ – Simply Beautiful Art Jun 2 '16 at 20:03

Let your sum be $P_m(r)$, which is a polynomial in $r$ of degree $2m-1$ for $m \ge 1$. The coefficient of $r^n$ in $P_m(r)$ seems to be a polynomial $Q_n(m)$ in $m$ of degree $n$. I haven't found a general pattern, but the first few are

$$\eqalign{ Q_0(m) = [r^0]\ P_m(r) &= 0 \cr Q_1(m) = [r^1]\ P_m(r) &= m \cr Q_2(m) = [r^2]\ P_m(r) &= -\dfrac{3}{2} m + \dfrac{3}{2} m^2 = \frac{3 m(m-1)}{2} \cr Q_3(m) = [r^3]\ P_m(r) &= \dfrac{23}{12} m - 3 m^2 + \dfrac{13}{12} m ^3 =\frac{m(m-1)(13m-23)}{12}\cr Q_4(m) = [r^4]\ P_m(r) &= -\frac{83}{36} m + \frac{323}{72} m^2 - \frac{97}{36} m + \frac{37}{72} m^4 =\frac{m(m-1)(m-2)(37m - 83)}{72}\cr Q_5(m) = [r^5]\ P_m(r) &= {\frac {1931}{720} m}-{\frac {1721}{288}m^2}+{\frac {445}{96} m^3}-{\frac {439}{288} m^4}+{\frac {263}{1440} m^5}\cr &= \frac{m(m-1)(m-2)(263m^2-1406m+1931)}{1440}\cr }$$ Of course $Q_n(m)$ has factors $m-j$ for $j \le n/2$ because the coefficient of $r^n$ in $P_j(r)$ is $0$ for such $j$.

The coefficient of $m^1$ in $Q_n(m)$ appears to be $$[m^1] Q_n(m) = (-1)^n n \left(-1 + \sum_{i=2}^n \dfrac{1}{i^2}\right) $$

  • $\begingroup$ Thanks for noticing. Fixed it. $\endgroup$ – Robert Israel Jun 2 '16 at 1:09

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.