Skip to main content

Chapter 5 Combinatorial Proof

Exercises Practice Problems

1. Creating a \(k\)-list.

Prove the following identity where we "treat element \(n\) as special." Think about this as writing a recipe, and then counting the number of ways that you can complete the recipe.

\begin{equation*} (n)_k = (n-1)_k + k \cdot (n-1)_{k-1}. \end{equation*}
2. Another Chairperson Identity.

Prove the following chairperson identity.

\begin{equation*} n 2^{n-1} = \sum_{k=1}^n k {n \choose k} \end{equation*}

  1. Explain how each side of the equation corresponds to a recipe for creating a chaired committee.

  2. Starting with the binomial theorem

    \begin{equation*} (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k}, \end{equation*}

    give another proof of this chairperson identity. (Hint: first, take the partial derivative of both sides with respect to \(x\text{.}\))

3. Picking a 2-Set.

Most introductory discrete mathematics books ask students to use induction to prove that

\begin{equation*} 1 + 2 + \cdots + n = \frac{n(n+1)}{2}. \end{equation*}

In this course, we recognize the right hand side is actually \({n+1 \choose 2}\text{.}\) In other words, we have

\begin{equation*} 1 + 2 + \cdots + n = {n+1 \choose 2}. \end{equation*}

Give a combinatorial proof of this identity about choosing a \(2\)-set from \([n+1]\text{.}\) Remember that an addition sign corresponds to "or." Hint: pick the largest element of the \(2\)-set first.

4. Combinatorial Proofs.

Give a combinatorial proof for each of the following identities. Each one involves splitting the original set into two or more subsets, and then performing the task at hand.

  1. .

    \begin{equation*} {3n \choose 3} = 3 {n \choose 3} + 6n {n \choose 2} + n^3. \end{equation*}

  2. .

    \begin{equation*} \sum_{k=0}^n \left( {n \choose k} \right)^2 = { 2n \choose n}. \end{equation*}

    Hint: you will need the identity \({r \choose s} = {r \choose r-s.}\text{.}\)

  3. .

    \begin{equation*} {n + m \choose r} = \sum_{i=0}^r {n \choose i} {m \choose r-i}. \end{equation*}
5. Subsets of \(n\) Without Successive Elements.

We define the following sets:

  • \({\mathcal{A}_n}\text{:}\) subsets of \([n]\) that do not contain successive elements

  • \({\mathcal{B}_n}\) ordered sums of 1's and 2's that add to \(n\text{.}\)

Show that \({\mathcal{A}_n}\) is in bijection with \({\mathcal{B}_{n+1}}\text{.}\)