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

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.

• For your original problem, isn't it equivalent to $\frac{\sum_{k=1}^m k^n}{m^{n+1}} \to \dfrac1{n+1}$? Commented Nov 29, 2021 at 20:20
• Could you expand on how you got this expression? Commented Nov 29, 2021 at 21:15

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.

• Thanks for the response - I'm sure your proof works, but since I'm trying to prove this from first principles I'd like to avoid proofs that themselves rely on integration. Commented Nov 29, 2021 at 23:10
• This direct proof is much appreciated - it's really neat! If you wouldn't mind, could you add back the original proof as well (with the beta integral)? It had some interesting maths in it as well. Commented Dec 4, 2021 at 12:13

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.

• Thanks a lot for this solution, it pretty much completely proves what I was trying to do. I'd just add that the final requirement is pretty easily done via induction, as is done here: brilliant.org/wiki/sum-of-n-n2-or-n3/#generalizations Commented Nov 29, 2021 at 23:09