2.4: Combinatorial Proofs

Last updated
Save as PDF

Page ID: 97855

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

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.

Example 2.13

Let $n$ be a positive integer. Use Figure 2.14 to explain why

$1+2+3+\cdot \cdot \cdot + n = \frac{n(n+1)}{2}$.

$Screen Shot 2022-02-23 at 1.56.16 PM.png$

Figure 2.14: The sum of first $n$ integers

Solution

Consider an $(n+1) \times (n+1)$ array of dots as depicted in Figure 2.14. There are $(n+1)^2$ dots altogether, with exactly $n+1$ on the main diagonal. The off-diagonal entries split naturally into two equal size parts, those above and those below the diagonal.

Furthermore, each of those two parts has $S(n) = 1+2+3+\cdot \cdot \cdot+n$ dots. It follows that

$S(n) = \frac{(n+1)^2-(n+1)}{2}$

and this is obvious! Now a little algebra on the right hand side of this expression produces the formula given earlier.

Example 2.15

Let $n$ be a positive integer. Explain why

$1+3+5+\cdot \cdot \cdot+2n-1 = n^2$

Screen Shot 2022-02-23 at 2.02.24 PM.png — Figure 2.16: The sum of the first $n$ odd integers

Solution: The left hand side is just the sum of the first $n$ odd integers. But as suggested in Figure 2.16, this is clearly equal to $n^2$.

Example 2.17

Let $n$ be a positive integer. Explain why

$\dbinom{n}{0}+\dbinom{n}{1}+\dbinom{n}{2}+\cdot \cdot \cdot+\dbinom{n}{n} = 2^n$.

Solution: Both sides count the number of bit strings of length $n$, with the left side first grouping them according to the number of 0's.

Example 2.18

Let $n$ and $k$ be integers with $0 \leq k \leq n$. Explain why

$\dbinom{n}{k+1} = \dbinom{k}{k} + \dbinom{k+1}{k} + \dbinom{k+2}{k} + \cdot \cdot \cdot +\dbinom{n-1}{k}$.

Solution: To prove this formula, we simply observe that both sides count the number of bit strings of length $n$ that contain $k+1$ 1's with the right hand side first partitioning them according to the last occurence of a 1. (For example, if the last 1 occurs in position $k+5$, then the remaining $k$ 1's must appear in the preceding $k+4$ positions, giving $C(k+4,k)$ strings of this type.) Note that when $k=1$ (so $k+1=2$), we have the same formula as developed earlier for the sum of the first $n$ positive integers.

Example 2.19

Explain the identity

$3^n = \dbinom{n}{0}2^0 + \dbinom{n}{1}2^1 + \dbinom{n}{2}2^2+ \cdot \cdot \cdot +\dbinom{n}{n}2^n$.

Solution: Both sides count the number of $\{0,1,2\}$-strings of length $n$, the right hand side first partitioning them according to positions in the string which are not 2. (For instance, if 6 of the positions are not 2, we must first choose those 6 positions in $C(n,6)$ ways and then there are $2^6$ ways to fill in those six positions by choosing either a 0 or a 1 for each position.)

Example 2.20

Explain why, for each non-negative integer $n$,

$\dbinom{2n}{n} = \dbinom{n}{0}^2 + \dbinom{n}{1}^2 + \dbinom{n}{2}^2 + \cdot \cdot \cdot +\dbinom{n}{n}^2$.

Solution: Both sides count the number of bit strings of length $2n$ with half the bits being 0's, with the right side first partitioning them according to the number of 1's occurring in the first $n$ positions of the string. Note that we are also using the trivial identity $\binom{n}{k} = \binom{n}{n-k}$.