$A$ and $B$ be the families of $n$-element subsets of $S=\{1,2,\ldots ,2n\}$ with respectively even and odd sums of elements. Compute $|A|-|B|$.

81 Views Asked by At

For a positive integer $n$, let $A$ and $B$ be the families of $n$-element subsets of $S=\{1,2,\ldots ,2n\}$ with respectively even and odd sums of elements. Compute $|A|-|B|$.


If we mark $E = \{2,4,...,2n\}$ and $O = \{1,3,...,2n-1\}$ then to get set in $A$ we have to take $2k$ elements in $O$ and $n-2k$ elements in $E$, and to get a set in $B$ we have to take $2k+1$ elements in $O$ and $n-2k-1$ elements in $E$. So $$|A| =\sum _{k=0}^{\infty}{n\choose 2k}{n\choose n-2k}$$ and
$$|B| =\sum _{k=0}^{\infty}{n\choose 2k+1}{n\choose n-2k-1}$$ Now this can be simplified like this:

$$|A|-|B| = {n\choose n}{n\choose 0} - {n\choose n-1}{n\choose 1} + {n\choose n-2}{n\choose 2}-{n\choose n-3}{n\choose 3}+...(-1)^n{n\choose 0}{n\choose n}$$

Clearly this can be simplified to $$|A|-|B| = {n\choose 0}^2 -{n\choose 1}^2 + {n\choose 2}^2-{n\choose 3}^2+...(-1)^n{n\choose n}^2$$

and it is $0$ for odd $n$. What about $n$ even? Can this be simplified?

2

There are 2 best solutions below

0
On BEST ANSWER

Here is an argument using generating functions: we have that the coefficient of $x^i y^j$ in $p(x, y) = (1+xy) (1+x^2 y) \cdots (1+x^{2n} y)$ is the number of subsets of $S$ with size $j$ and sum $i$. Now, we are interested only in the case $j = n$ so we take the "coefficient" of $y^n$ in $p \in (\mathbb{Z}[x])[y]$, which gives a polynomial in $x$. Then, the ultimate answer we want is taking the sum of even-power coefficients in this polynomial minus the sum of odd-power coefficients. That is the same as substituting $x := -1$.

However, it is not hard to see that the operations of taking the coefficient of $y^n$ and of substituting $x := -1$ essentially commute; so the answer you want is also the coefficient of $y^n$ in $\prod_{k=1}^{2n} (1 + (-1)^k y) = (1 - y^2)^n$. (Here, each consecutive pair of terms in the product multiplies to $(1-y) (1+y) = 1-y^2$.) Now, expanding using the binomial theorem, it is easy to see that this is equal to 0 if $n$ is odd, or to $(-1)^{n/2} \binom{n}{n/2}$ if $n$ is even.

0
On

Your sum is equal to

$$\binom{n}0^2-\binom{n}1^2+\cdots+(-1)^n\binom{n}n^2 = \begin{cases} (-1)^k\frac{(2k)!}{k!^2}, & \text{if $n=2k$} \\ 0, & \text{if $n$ is odd} \end{cases}$$

Several proofs are given here.