4
$\begingroup$

Question: Is there a closed-form expression for the following sum

$$ F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1} $$

where $z\in\mathbb{C}$, and $r$, $k$ are non-negative integers.

Remark: Obviously, the above expression is a polynomial of degree $r$. However, I am interested in "alternative" expressions for it as later on I will need to compute residues of the product of above functions (see below).

Motivation: I am trying to compute a much nastier expression involving sum over multisets and ratios of multinomial coefficients:

$$ \sum_{(n_1,\ldots,n_d)\vdash N-k}\dfrac{{{k} \choose {k_1,k_2,\ldots,k_d}} {{N-k} \choose {n_1,n_2,\ldots,n_d}} }{ {{N} \choose {n_1+k_1,n_2+k_2,\ldots,n_d+k_d}}}\label{ssum}\tag{2} $$

where $N,k$ are fixed non-negative integers and $(k_1,\ldots,k_d)$ is fixed and satisfies $(k_1,\ldots,k_d)\vdash k$.

I got expression $\eqref{sum}$ by trying to compute $\eqref{ssum}$ explicitly via the integral representation of Kronecker delta.

$\endgroup$
  • $\begingroup$ Writing $\frac{F(z,k,r)}{k!} = \sum_{n=0}^r \frac{\Gamma(n+1)}{\Gamma(n+k+1)} z^n = \sum_{n=0}^r\frac{z^n}{(n)_k}$ looks close to certain hypergeometricish functions I have seen but I am unsure if I know the name of them. $\endgroup$ – Daniel Parry Sep 21 '15 at 12:11
  • 1
    $\begingroup$ In case it is of any help, the generating function $G(x)=\sum_r F(z,k,r)x^r$ appears to satisfy $x(x-1)(xz-1)G'(x) + \big(x(2x-1)z -(k+1)x+k\big)G(x) - k = 0$. $\endgroup$ – Martin Rubey Sep 21 '15 at 13:56
  • $\begingroup$ (The generating function according to $k$ does not appear to be as nice.) $\endgroup$ – Martin Rubey Sep 21 '15 at 14:04
  • 3
    $\begingroup$ Mathematica writes it out as a difference of two ${}_2F_1$ hypergeometrics, but that seems to be perhaps not the "closed-form" you are after! $\endgroup$ – Suvrit Sep 21 '15 at 15:11
  • $\begingroup$ @Suvrit Note that the first of the hypergeometrics does not involve $r$ $\endgroup$ – Igor Rivin Sep 21 '15 at 15:29
7
$\begingroup$

Let's solve Martin Rubey's differential equation, which I write as $$g(x)G'(x) = f_1(x)G(x) + f_0(x),$$ where $g(x) = x(x-1)(xz-1)$, $f_1(x) = -x(2x-1)z+(k+1)x-k$, and $f_0(x)=k$.

Then by the general formula, we compute $$F(x) = \int \frac{f_1(x)}{g(x)}\,dx = (k - 1) \ln(x z - 1) - k\ln(x) - \ln(x - 1),$$ and thus $$e^{F(x)} = \frac{(xz-1)^{k-1}}{x^k(x-1)}.$$ Then since $G(0)=1$, we get $$G(x) = \frac{k(1-xz)^{k-1}}{x^k(1-x)} \int \frac{x^{k-1}}{(1-xz)^k}\,dx$$ $$= \frac{(1-xz)^{k-1}}{1-x} \sum_{t\geq 0} \frac{k}{k+t} \binom{-k}{t} (-z)^t x^t$$ $$ = \frac{(1-xz)^{k-1}}{1-x}\ {}_2F_1(k,k+2;k+1;-xz).$$


Extracting the coefficient of $x^r$: $$[x^r]\ G(x) = \sum_{n\leq r}(-z)^n\sum_{t\geq 0} \frac{k}{k+t} \binom{-k}{t} \binom{k-1}{n-t},$$ we arrive at a remarkable identity $$\sum_{t\geq 0} \frac{k}{k+t} \binom{-k}{t} \binom{k-1}{n-t} = \frac{(-1)^n}{\binom{n+k}k},$$ which holds for all $n\geq 0$ and $k\geq 1$.

$\endgroup$
  • 1
    $\begingroup$ The identity is a special case of Saalschütz's theorem. It can be generalized to $$\sum_{t\geq 0} \frac{a}{a+t} \binom{-k}{t} \binom{k-1}{n-t} = (-1)^n\frac{\binom{a}{k}}{\binom{n+a}k}.$$ $\endgroup$ – Ira Gessel Apr 20 '18 at 22:51
  • $\begingroup$ @IraGessel: Thanks for the pointer! I suspected it'd be well-known. $\endgroup$ – Max Alekseyev Apr 21 '18 at 0:10
  • 1
    $\begingroup$ Thank you for the answer. I like it a lot. In the end we managed to proceed without using the generating function explicitly, see page 22 of journals.aps.org/prx/abstract/10.1103/PhysRevX.6.041044 (I realize that it is not straightforward to translate these computations to the original question...). Anyway, let me remark that in a variety of cases group-theoretic methods can yield complicated combinatoric identities. $\endgroup$ – Michał Oszmaniec Nov 3 '18 at 18:11

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.