Exercise 1.4.1 (Combinatorial proof of $\sum_{k=0}^n \binom{n}{k} = 2^n$.)

Question

Use the binomial theorem to show that
$$\sum_{k=0}^n \binom{n}{k} = 2^n.$$
Can you give a combinatorial proof of this?

Richard Ganaye · Accepted Answer

\begin{proof} 
a) By the binomial theorem, for any real numbers $x$ and $y$,
$$\sum_{k=0}^n \binom{n}{k} x^k y^{n-k} = (x+y)^n.$$
For $x=y=1$, we obtain
$$\sum_{k=0}^n \binom{n}{k}  = 2^n.$$

\bigskip
b) Let $E$ be a set of cardinality $n$, for instance $E = [\![1,n]\!]$. Let $\mathscr{P}_k(E)$ denotes the set of  subsets of $E$ with cardinality $k$:
$$\mathscr{P}_k(E) = \{ A \in \mathscr{P}(E): |A| = k\}.$$
Then every subset of $E$ has a cardinality $k$, where $0 \leq k \leq n$, so
$$\mathscr{P}(E) = \bigcup_{k=0}^n \mathscr{P}_k(E),$$
and this union is a disjoint union: 
$$0 \leq k < l \leq n \Rightarrow  \mathscr{P}_k(E) \cap  \mathscr{P}_l(E)=\varnothing.$$
In other words, $( \mathscr{P}_k(E))_{k\in  [\![0,n]\!]}$ is a partition of $\mathscr{P}(E) $. Therefore
$$|\mathscr{P}(E) | = \sum_{k=0}^n |\mathscr{P}_k(E)|.$$
Since $|\mathscr{P}(E) | = 2^n$, and $|\mathscr{P}_k(E)| = \binom{n}{k}$, this gives
$$2^n = \sum_{k=0}^n \binom{n}{k}.$$
\end{proof}

Exercise 1.4.1 (Combinatorial proof of $\sum_{k=0}^n \binom{n}{k} = 2^n$.)

Answers

Comments

Exercise 1.4.1 (Combinatorial proof of $\sum_{k=0}^n \binom{n}{k} = 2^n$.)

Answers

Comments

Add answer