How do I prove that, for set $X$,
$$\sum_{S\subseteq X, S\neq \emptyset}\frac{(-1)^{|S|}}{|X|+|S|} = \frac{|X|!(|X|-1)!}{(2|X|)!}$$
I have been around this exercise all day and would much appreciate your help.
Asked
Active
Viewed 140 times
5
-
What is SCX? Also note that MathJax can help you format your question is more reader-friendly way. – Julien May 26 '13 at 18:43
-
@Marta, I've done my best typesetting your question; please let me know if this is what you meant. – vadim123 May 26 '13 at 18:48
-
yes, thank you,that is exactly what I meant. – Maria May 26 '13 at 18:49
-
1That seems odd, since if $|X|=1$, the LHS is $\frac{-1}{2}$ while the RHS is $\frac{1}{2}$. – vadim123 May 26 '13 at 18:49
-
What does this mean for an infinite $X$? What is $\dfrac{(-1)^{\aleph_0}}{\aleph_2}$? – Asaf Karagila May 26 '13 at 18:55
-
I have no idea. This is a recurrence exercise, but this is all the information I got. – Maria May 26 '13 at 18:59
-
1The formula holds for $|X|=1,2$ if you add $\emptyset$ to the summation of the lhs. Otherwise it is false. – Julien May 26 '13 at 20:16
1 Answers
7
Let us denote $n = |X|$. Then
\begin{align*} \sum_{S\subset X} \frac{(-1)^{|S|}}{|X|+|S|} &= \sum_{k=0}^{n} \binom{n}{k} \frac{(-1)^{k}}{n+k} = \sum_{k=0}^{n} \binom{n}{k} (-1)^{k} \int_{0}^{1} x^{n+k-1} \, dx \\ &= \int_{0}^{1} \sum_{k=0}^{n} \binom{n}{k} (-1)^{k} x^{n+k-1} \, dx = \int_{0}^{1} x^{n-1} (1 - x)^{n} \, dx \\ &= \beta(n, n+1) = \frac{\Gamma(n)\Gamma(n+1)}{\Gamma(2n+1)} = \frac{(n-1)!n!}{(2n)!} \end{align*}
as desired.
Sangchul Lee
- 167,468