call the integral and substitute and for . then the Jacobian would be and thus
where , as usual, is the beta function. it's easy now to see that
First note that what we are doing is choosing subsets of size by the following procedure:
1. Choose a subset of size .
2. Now choose a subset of size from the subset chosen in 1 - if possible.
It is clear that we are overcounting, but by how much? Well, any subset of size is part of subsets of size - that's the number of ways of completing the set -, that is
So in fact we have
Now plug and we get
EDIT: I am going to add a couple of problems for you to enjoy. (Rofl)
1. where is Euler's Totien function.
2. This one is beautiful too, let we define to be the number of pairs of integers that satisfy and - such a pair is called an inversion.
What is the average number of inversions ?
Here are a few sums for you to calculate. However these may be too easy...
and one that involves much more algebra:
Where is the 'th harmonic number.
Here's my rebuttal:
For , evaluate .