Exercise 2, § 5

Tag 03ME, permanent. Cite it as [Bourbaki, Tag 03ME].

Theory of Sets, III, 235

If $n \geqslant 1$ , prove the relation

\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n\binom{n}{n} = 0.

(Define a one-to-one correspondence between the set of subsets of $[1, n]$ which have an even number of elements, and the set of subsets of $[1, n]$ which have an odd number of elements. Distinguish between the cases $n$ even and $n$ odd.)

Solution

This solution was written by nemotron-3-ultra-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

Let $n \geqslant 1$ be an integer. Set $E = [1, n]$ . For any subset $X \subset E$ , let $|X|$ denote its cardinal. Define

\mathscr{E}_{\text{even}} = \{ X \subset E \mid |X| \text{ is even} \}, \qquad \mathscr{E}_{\text{odd}} = \{ X \subset E \mid |X| \text{ is odd} \}.

By Corollary 1 to Proposition 11, the binomial coefficient

\binom{n}{k}

is the number of subsets of

E

with exactly

k

elements. Hence

\sum_{k=0}^{n} (-1)^k \binom{n}{k} = \sum_{\substack{k=0 \\ k \text{ even}}}^{n} \binom{n}{k} - \sum_{\substack{k=0 \\ k \text{ odd}}}^{n} \binom{n}{k} = |\mathscr{E}_{\text{even}}| - |\mathscr{E}_{\text{odd}}|.

We shall construct a bijection between

\mathscr{E}_{\text{even}}

and

\mathscr{E}_{\text{odd}}

, which will imply

|\mathscr{E}_{\text{even}}| = |\mathscr{E}_{\text{odd}}|

and therefore the desired equality.

We distinguish two cases.

Case 1: $n$ is odd. Consider the complement map $f : \mathscr{P}(E) \to \mathscr{P}(E)$ defined by $f(X) = E \setminus X$ . This map is an involution, hence a bijection. For any $X \subset E$ , we have $|f(X)| = n - |X|$ (by the standard property of cardinals of finite sets). Since $n$ is odd, $|X|$ is even if and only if $n - |X|$ is odd. Therefore $f$ maps $\mathscr{E}_{\text{even}}$ onto $\mathscr{E}_{\text{odd}}$ and $\mathscr{E}_{\text{odd}}$ onto $\mathscr{E}_{\text{even}}$ . The restriction of $f$ to $\mathscr{E}_{\text{even}}$ is a bijection from $\mathscr{E}_{\text{even}}$ to $\mathscr{E}_{\text{odd}}$ .

Case 2: $n$ is even. Since $n \geqslant 1$ , the set $E$ is non‑empty; choose an element $a \in E$ , for instance $a = 1$ . Define $g : \mathscr{P}(E) \to \mathscr{P}(E)$ by $g(X) = X \mathbin{\triangle} \{a\}$ , the symmetric difference of $X$ with the singleton $\{a\}$ . Equivalently,

g(X) = \begin{cases} X \cup \{a\} & \text{if } a \notin X,\\ X \setminus \{a\} & \text{if } a \in X. \end{cases}

The map

g

is an involution, hence a bijection. For any

X \subset E

, the cardinalities of

X

and

g(X)

differ by exactly

1

, so their parities are opposite. Thus

g

exchanges

\mathscr{E}_{\text{even}}

and

\mathscr{E}_{\text{odd}}

, and its restriction to

\mathscr{E}_{\text{even}}

is a bijection onto

\mathscr{E}_{\text{odd}}

In both cases we have established a bijection between $\mathscr{E}_{\text{even}}$ and $\mathscr{E}_{\text{odd}}$ . Consequently $|\mathscr{E}_{\text{even}}| = |\mathscr{E}_{\text{odd}}|$ , and

\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n \binom{n}{n} = 0.

Cited by

Exercise 3, § 5

Cites

Nothing.