# Evaluate $1 + \sum_{i=0}^{n-2} [ \prod_{k=0}^{i} (n-k)/(r-k) ]$

Is there a way in which the expression

$$1 + \sum_{i=0}^{n-2} \prod_{k=0}^{i} \dfrac{n-k}{r-k}$$

may be simplified?

It would simplify some equations I am working with.

-
This is an expression, not an equation. – alex.jordan Feb 21 '12 at 20:53
You could try to ask Wolfram. – draks ... Feb 21 '12 at 21:17
I am curious how this came up... – Aryabhata Feb 21 '12 at 23:51

First, using recurrence equation for Euler's $\Gamma$-function: $$\prod_{k=0}^m \frac{n-k}{r-k} = \frac{\Gamma(n+1)}{\Gamma(n-m)} \cdot \frac{\Gamma(r-m)}{\Gamma(r+1)}$$ Then, changing summation variable as $m \to n-2-m$: $$1 + \sum_{m=0}^{n-2} \frac{\Gamma(n+1)}{\Gamma(n-m)} \cdot \frac{\Gamma(r-m)}{\Gamma(r+1)} = 1 + \sum_{m=0}^{n-2} \frac{\Gamma(n+1)}{\Gamma(n-(n-2-m))} \cdot \frac{\Gamma(r-(n-m-2))}{\Gamma(r+1)} = \\ 1 + \frac{\Gamma(n+1)}{\Gamma(r+1)} \sum_{m=0}^{n-2} \frac{\Gamma(m+r+2-n)}{\Gamma(m+2)} = 1 + \frac{\Gamma(n+1)}{\Gamma(r+1)} \sum_{m=0}^{n-2} \frac{\Gamma(m+r+2-n)}{\Gamma(m+2)}$$ Now the last sum is just a hypergeometric series: $$\frac{\Gamma(n+1)}{\Gamma(r+1)} \sum_{m=0}^{n-2} \frac{\Gamma(m+r+2-n)}{\Gamma(m+2)} = \frac{\Gamma(n+1) \Gamma(1+r-n)}{\Gamma(r+1)} \sum_{m=0}^{n-2} \frac{\Gamma(m+r+2-n)}{\Gamma(m+2) \Gamma(1+r-n)} = \\ \frac{1}{\binom{r}{n}} \sum_{m=0}^{n-2} \binom{m+r-n+1}{m+1} = \frac{n}{r-n+1} - \frac{1}{\binom{r}{n}}$$ The last equality follows because $s_{m+1} - s_m = \binom{m+r-n+1}{m+1}$, where $$s_m = \frac{m+1}{r-n+1}\binom{m+r-n+1}{m+1}$$ And therefore the original sum telescopes $$\sum_{m=0}^{n-2} \binom{m+r-n+1}{m+1} = \sum_{m=0}^{n-2} (s_{m+1}-s_m) = s_{n-1} - s_0$$

It now remains to compute $s_{m+1}-s_m$: $$s_{m+1} = \frac{m+2}{r-n+1} \binom{m+r-n+2}{m+2} = \frac{m+2}{r-n+1} \cdot \frac{m+r-n+2}{m+2} \binom{m+r-n+1}{m+1} = \\ s_m + \binom{m+r-n+1}{m+1}$$

-
Great job. All I could tell was that it was a very bizarre instance of the falling factorial. Is there perhaps a more elementary way to approach this? I don't immediately see that as likely, as it's unlikely that you or anyone else would step over an elementary method. – 000 Feb 21 '12 at 21:40
thankyou so much. – Hemantika Feb 24 '12 at 8:33

I believe your sum comes out to:

$$\frac{r+1}{r-n+1} - \frac{1}{\binom{r}{n}}$$

We can prove this using Beta integrals. We have the identity:

$$\frac{1}{\binom{r}{k}} = (r+1)\int_{0}^{1} t^{r-k} (1-t)^k dt$$

What you have is

$$1+\sum_{k=1}^{n-1} \frac{\binom{n}{k}}{\binom{r}{k}}$$

Now

$$\sum_{k=1}^{n-1} \frac{\binom{n}{k}}{\binom{r}{k}} = \sum_{k=1}^{n-1} (r+1)\int_{0}^{1} \binom{n}{k} t^{r-k} (1-t)^k dt =$$

$$(r+1)\int_{0}^{1} \sum_{k=1}^{n-1} \binom{n}{k} t^{r-k} (1-t)^k dt =$$

$$(r+1)\int_{0}^{1} t^{r-n} \sum_{k=1}^{n-1} \binom{n}{k} t^{n-k} (1-t)^k dt =$$

$$(r+1)\int_{0}^{1} t^{r-n} (1 - t^n - (1-t)^n) dt =$$ $$(r+1)\int_{0}^{1} t^{r-n} - t^r - t^{r-n}(1-t)^n dt =$$ $$\frac{r+1}{r-n+1} - 1 - (r+1)\int_{0}^{1}t^{r-n}(1-t)^n dt =$$

$$\frac{r+1}{r-n+1} - 1 - \frac{1}{\binom{r}{n}}$$

(at the last step we used the Beta integral identity mentioned earlier).

Thus the sum you seek is

$$\frac{r+1}{r-n+1} - \frac{1}{\binom{r}{n}}$$

Here are a couple of answers which use Beta integral:

Formula for the harmonic series $H_n = \sum_{k=1}^n 1/k$ due to Gregorio Fontana

http://math.stackexchange.com/a/6533/1102

-
thankyou so much. – Hemantika Feb 24 '12 at 8:33