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$
7
  • $\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$ Commented Sep 21, 2015 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$ Commented Sep 21, 2015 at 13:56
  • $\begingroup$ (The generating function according to $k$ does not appear to be as nice.) $\endgroup$ Commented Sep 21, 2015 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
    Commented Sep 21, 2015 at 15:11
  • $\begingroup$ @Suvrit Note that the first of the hypergeometrics does not involve $r$ $\endgroup$
    – Igor Rivin
    Commented Sep 21, 2015 at 15:29

1 Answer 1

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$
3
  • 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
    Commented Apr 20, 2018 at 22:51
  • $\begingroup$ @IraGessel: Thanks for the pointer! I suspected it'd be well-known. $\endgroup$ Commented Apr 21, 2018 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$ Commented Nov 3, 2018 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.