$\sum_{i=k}^{z} \frac{(-1)^{i-k} {z\choose i}{i\choose k}}{i+1} = \frac{1}{z+1} ​$ - combinatorial identity

Question

I'm trying to prove, from first principles, that:

$$\int_a^bx^n = \frac{b^{n+1}-a^{n+1}}{n+1} $$

I know of the geometrical argument where you take rectangles of increasingly small width (i.e. dimension in the $x$ axis) which add up nicely via the rule for summation of a geometric series. However, I wanted to derive this same identity via rectangles of equal width (where you take the limit as the width goes to 0). I eventually reduced this problem to proving the following:

$$\forall k,x \in \mathbb{Z} \text{ such that } 0 \leq k \leq z: $$ $$\sum_{i=k}^{z} \frac{(-1)^{i-k} {z\choose i}{i\choose k}}{i+1} = \frac{1}{z+1} $$

I'm not sure how to prove this. I could rewrite this as:

$${z\choose k }\sum_{i=k}^{z} \frac{(-1)^{i-k} {{z-k}\choose {i-k}}}{i+1} = \frac{1}{z+1} $$

But I'm not sure if that's useful. Any help for this last identity would be much appreciated.

Answer 1

You can given a direct proof of your equality using the principle of inclusion-exclusion.

Question: Imagine shuffling a deck of $z+1$, with $k$ black cards, $1$ red card, and $z-k$ white cards. What is the probability that the shuffled deck is ordered so all the black cards are grouped together on the bottom, all of the white cards are grouped together on top, and the red card is between the groups?

Answer 1: By counting favorable outcomes, the answer is simply $$\frac1{\binom{z}k(z+1)}$$

Answer 2: Let $B$ be the event that the red card is above all black cards, so $P(B)=1/(k+1)$. For each $i\in \{1,\dots,z-k\}$, let $W_i$ be the event that the $i^\text{th}$ white card is below the red card. We want to find $$ P(B\cap W_1^c\cap W_2^c\cap \dots \cap W_{z-k}^c) $$ Using the symmetry of the white cards, we can write the PIE expression as for the above as $$ P(B)-\binom{z-k}1 P(B\cap W_1)+\binom{z-k}2 P(B\cap W_1\cap W_2)-\dots \\+(-1)^i \binom{z-k}i P(B\cap W_1\cap \dots\cap W_i) +\dots\tag1 $$ In words, we start with a favorable event $B$, and for each bad event $W_i$, we subtract the instances where both $B$ and $W_i$ occur. We then correct for double subtraction by adding in the outcomes where two bad events $W_i$ and $W_j$ have occurred, then correct for triple subtractions, and so on. Note that $$ P(B\cap W_1\cap \dots \cap W_i)=\frac1{k+i+1},\tag2 $$ since among the $k$ black cards, the $i$ white cards numbered $1$ to $i$, and the red card, any of the $k+i+1$ cards is equally likely to be on top. Substituting $(2)$ into $(1)$, we conclude $$ \text{answer} = \sum_{i=0}^{z-k} (-1)^i\binom{z-k}i\frac1{i+k+1} $$

Since these two answers to the question must be the same, we have proved $$ \sum_{i=0}^{z-k} (-1)^i\binom{z-k}i\frac1{i+k+1}=\frac1{\binom{z}k(z+1)} $$ which is equivalent to your identity, after re-indexing the sum.

---

Old Answer: To prove your identity, start with the equation $$ x^{k}(1-x)^{z-k}=\sum_{i=0}^{z-k}(-1)^i \binom{z-k}i x^{i+k} $$ Integrate both sides from $0$ to $1$ with respect to $x$: $$ \int_0^1 x^{k}(1-x)^{z-k}\,dx =\sum_{i=0}^{z-k} \frac{(-1)^i\binom{z-k}{i}}{i+k+1} =\sum_{i=k}^{z} \frac{(-1)^{i-k}\binom{z-k}{i-k}}{i+1} $$ Finally, evaluate the integral. This is the well-known Beta integral, and we have $$ \int_0^1 x^{k}(1-x)^{z-k}\,dx=\mathrm{B}(k+1,z-k+1)=\frac{k!(z-k)!}{(z+1)!}=\frac1{(z+1)\binom{z}k} $$ Putting this altogether, your identity is proved.

Answer 2

This is in response to the proposer's response to my comment on the question. (Nothing original here.)

To show that $\int_a^bx^ndx = \frac{b^{n+1}-a^{n+1}}{n+1} $ it is enough to show that $\int_0^ax^ndx = \frac{a^{n+1}}{n+1} $.

Dividing $[0, a]$ into $m$ intervals, they are $[\dfrac{a(k-1)}{m}, \dfrac{ak}{m}] $ for $k=1$ to $m$.

The integral over each interval, $I_k =\int_{\frac{a(k-1)}{m}}^{\frac{ak}{m}} x^n dx $ satisfies $\frac{a}{m}(\frac{a(k-1)}{m})^n \lt I_k \lt \frac{a}{m}(\frac{ak}{m})^n $ since $x^n$ is increasing in the interval.

Summing these, if $I=\sum_{k=1}^m I_k $, $\frac{a^{n+1}}{m^{n+1}}\sum_{k=1}^m (k-1)^n \lt I \lt \frac{a^{n+1}}{m^{n+1}}\sum_{k=1}^mk^n $.

Once you show that $\lim_{m \to \infty} \frac1{m^{n+1}}\sum_{k=1}^m k^n \to \dfrac1{n+1} $ you are done.