Abstract Nonsense

Crushing one theorem at a time

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.

Advertisements

October 26, 2010 - Posted by | Analysis, Computations, Fun Problems | , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: