How to calculate this triple summation?

Question

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?

Answer 1

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*}

Comment:

• 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

Answer 2

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.

Answer 3

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) $$