Identity involving falling factorial

Question

Let $(x)_n$ denote the falling factorial, $$(x)_n = x(x-1) \dots (x - n + 1).$$

I came across the following identity in trying to solve another problem. $$\sum_{k=1}^m \frac{(a)_k}{(x)_k} = \frac{a}{x - a + 1}\left( 1 - \frac{(a-1)_m}{(x)_m}\right).$$

This identity allows you to find closed forms for sums such as $$\sum_{k=0}^m \frac{\Gamma(x + k)}{\Gamma(y + k)}$$ or $$\sum_{k = 0}^c \frac{a \choose k}{b \choose k}.$$

It is similar to a series mentioned here (Infinite sum of falling factorial quotients. ), except that my sum is finite.

I proved the identity by induction, which isn't too hard, as long as you know what you're looking for. I have a couple of questions, though.

• I tried to find this identity mentioned somewhere, but couldn't find it. Is it well-known, or a special case of a better known identity?

• I found the expression on the right-hand side through trial and error. Is there a more natural derivation of the identity, particularly if you know the left-hand side and are looking for the right-hand side?

For example, after multiplying through by $(x - a + 1)(x)_m$, the identity becomes one of polynomials in $a$ and $x$, hence it would be sufficient to prove it for sufficiently large integers $a$ and $x$. Perhaps there is a combinatorial explanation.

Answer 1

Integrals and Series, Prudnikov, et. al. has in its Finite Sum section, as entry 4.2.8.1

$$ \sum_{k=m}^n \frac{\binom{a}{k}}{\binom{b}{k}} = \frac{b+1}{b-a+1}\Big( \frac{\binom{a}{m}}{\binom{b+1}{m}} - \frac{\binom{a}{n +1}}{\binom{b+1}{n+1}} \Big) $$ Thus the OP's sum is known and the above is a generalization. I have not tried to prove it.

Answer 2

Here is a probabilistic proof of the identity in skbmoore's answer, from which the OP's identity follows.

Since the identity can be expressed as a polynomial in the variables $a, b$, it is enough to prove it when $a$ is a positive integer and $b \geq a$ is an integer.

Draw elements at random from the set $\{1, 2, \dots, b + 1\}$, without replacement, and stop when you pick the first element that is not in $\{1, 2, \dots, a\}$. Let $K + 1$ be the number of elements drawn in all.

Then the probability that $m \leq K \leq n$ can be calculated in two ways.

First, it is the probability $\frac{a \choose m}{{b + 1} \choose m}$ of drawing the first $m$ elements in the set $\{1, 2, \dots, a\}$, minus the probability $\frac{a \choose {n+1}}{{b + 1} \choose {n+1}}$ of drawing the first $n+1$ elements in that set.

Second, it is the sum over $k = m, \dots, n,$ of the probability that K = k. Reversing the order of the draw, this is the same as the probability $(b + 1 - a)/(b + 1)$ of picking the first element outside the set $\{1, 2, \dots, a\}$, multiplied by the probability in that case of picking the next $k$ elements in that set, which is $\frac{a \choose k}{b \choose k}$.

Answer 3

We prove \begin{align*} \sum_{k=m}^n\frac{\binom{a}{k}}{\binom{b}{k}}=\frac{b+1}{b-a+1}\left(\frac{\binom{a}{m}}{\binom{b+1}{m}}-\frac{\binom{a}{n+1}}{\binom{b+1}{n+1}}\right)\tag{1} \end{align*}

We start with the right-hand side of (1) and obtain \begin{align*} \color{blue}{\frac{b+1}{b-a+1}}&\color{blue}{\left(\frac{\binom{a}{m}}{\binom{b+1}{m}}-\frac{\binom{a}{n+1}}{\binom{b+1}{n+1}}\right)}\\ &=\frac{b+1}{b-a+1}\sum_{k=m}^n\left(\frac{\binom{a}{k}}{\binom{b+1}{k}}-\frac{\binom{a}{k+1}}{\binom{b+1}{k+1}}\right)\tag{2}\\ &=\frac{b+1}{b-a+1}\sum_{k=m}^n\frac{\binom{a}{k}}{\binom{b}{k}}\left(\frac{1}{\frac{b+1}{b-k+1}}-\frac{\frac{a-k}{k+1}}{\frac{b+1}{k+1}}\right)\tag{3}\\ &=\frac{b+1}{b-a+1}\sum_{k=m}^n\frac{\binom{a}{k}}{\binom{b}{k}}\left(\frac{b-k+1}{b+1}-\frac{a-k}{b+1}\right)\\ &=\frac{1}{b-a+1}\sum_{k=m}^n\frac{\binom{a}{k}}{\binom{b}{k}}\left(b-k+1-(a-k)\right)\\ &\,\,\color{blue}{=\sum_{k=m}^n\frac{\binom{a}{k}}{\binom{b}{k}}} \end{align*} and the claim (1) follows.

Comment:

• In (2) we write the expression as telescoping sum.

• In (3) we factor out $\frac{\binom{a}{k}}{\binom{b}{k}}$ and simplify in the following steps.