# Abstract Nonsense

## Interesting Combinatorial Sum

Point of post: This is just an interesting combinatorial sum I solved on AOPS a few minutes ago. I mention it because, while sometimes less elegant, one must remember to never disregard “continuous” math even when one is working in “discrete” areas.

Problem: For $n,k\in\mathbb{N}$ such that $n-k-1$ prove that

$\displaystyle \sum_{t=0}^{n-k-1}\frac{(-1)^t}{k+t+1}{{n-k-1}\choose{t}}=\frac{k!(n-k-1)!}{n!}$

Proof: The first thing one might notice is that

$\displaystyle \frac{1}{t+k+1}=\int_0^1 x^{t+k}dx$

so that

$\displaystyle \sum_{t=0}^{n-k-1}\frac{(-1)^t}{k+t+1}{{n-k-1}\choose{t}}=\sum_{t=0}^{n-k-1}\left(\int_0^1 x^{k+t}dx\right)(-1)^t{{n-k-1}\choose{t}}dx$

But, rearranging this we arrive at

$\displaystyle \int_0^1 x^k\sum_{t=0}^{n-k-1}x^t (-1)^t{{n-k-1}\choose{t}}dx=\int_0^1 x^k\sum_{t=0}^{n-k-1}x^t (-1)^{-t}{{n-k-1}\choose{t}}dx$

which equals

$\displaystyle \frac{1}{(-1)^{n-k-1}}\int_0^1 x^k\sum_{t=0}^{n-k-1}x^t (-1)^{n-k-1-t}{{n-k-1}\choose{t}}dx$

but appealing to the Binomial Theorem we see that the above is equal to

$\displaystyle \frac{1}{(-1)^{n-k-1}}\int_0^1 x^k (x-1)^{n-k-1}dx=\int_0^1 x^k(1-x)^{n-k-1}dx=\text{B}(k+1,n-k)$

where $\text{B}(x,y)$ is the Beta Function. But, appealing to an alternative form of the Beta function we see that the sum is equal to

$\displaystyle \frac{\Gamma(k+1)\Gamma(n-k)}{\Gamma(k+1+n-k)}=\frac{k!(n-k-1)!}{n!}$

where $\Gamma(x)$ is the Gamma Function.