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$ Jan 7, 2014 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, 2014 at 22:59
  • $\begingroup$ But what is the problem? $\endgroup$ Jan 7, 2014 at 23:00
  • 2
    $\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, 2014 at 23:06

3 Answers 3


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$ Jun 7, 2016 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$ Jun 7, 2016 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$ Jun 7, 2016 at 21:15
  • $\begingroup$ Haha, take that for a closed form lol. I do think attempting to summate that is hopeless. $\endgroup$ Jun 7, 2016 at 21:16
  • 1
    $\begingroup$ Sh.... I think its nice too. :-) wolframalpha is awesome. $\endgroup$ Jun 7, 2016 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$ Jun 1, 2016 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$ Jun 2, 2016 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$ Jun 2, 2016 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$ Jun 2, 2016 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$ Jun 2, 2016 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$ Jun 2, 2016 at 1:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .