2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The easy way to see this if $n$ is odd is to note that the total sum of all elements is odd, so that each set in $A$ has its complement in $B$ and vice versa. $\endgroup$ – Mark Bennet Jun 22 '18 at 18:53
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.