Section2.4Combinatorial Proofs¶ permalink

Combinatorial arguments are among the most beautiful in all of mathematics. Oftentimes, statements that can be proved by other, more complicated methods (usually involving large amounts of tedious algebraic manipulations) have very short proofs once you can make a connection to counting. In this section, we introduce a new way of thinking about combinatorial problems with several examples. Our goal is to help you develop a “gut feeling” for combinatorial problems.

Example2.13

Let \(n\) be a positive integer. Use Figure 2.14 to explain why \begin{equation*} 1+2+3+\dots+n=\frac{n(n+1)}{2}. \end{equation*}

Figure2.14The sum of the first \(n\) integers

Solution

Example2.15

Let \(n\) be a positive integer. Explain why \begin{equation*} 1+3+5+\dots+2n-1=n^2. \end{equation*}

Figure2.16The sum of the first \(n\) odd integers

Solution

Example2.17

Let \(n\) be a positive integer. Explain why \begin{equation*} \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}=2^n. \end{equation*}

Solution

Example2.18

Let \(n\) and \(k\) be integers with \(0\le k\lt n\). Explain why \begin{equation*} \binom{n}{k+1} = \binom{k}{k} + \binom{k+1}{k} + \binom{k+2}{k} +\dots+ \binom{n-1}{k}. \end{equation*}

Solution

Example2.19

Explain the identity \begin{equation*} 3^n=\binom{n}{0}2^0+\binom{n}{1}2^1+\binom{n}{2}2^2+ \dots+\binom{n}{n}2^n. \end{equation*}

Solution

Example2.20

Explain why, for each non-negative integer \(n\), \begin{equation*} \binom{2n}{n}= {\binom{n}{0}}^2+{\binom{n}{1}}^2+{\binom{n}{2}}^2+\dots+ {\binom{n}{n}}^2. \end{equation*}

Solution