Proposition 22.4.2.
For \(n \ge 2\) and \(1\le k \le n-1\text{,}\) we have \(\combinationalt{n}{k} = \combinationalt{n-1}{k-1} + \combinationalt{n-1}{k} \text{.}\)
Section 22.4 Properties
Note: In this section we will use the alternative notation \(\combinationalt{n}{k}\) in place of \(\combination{n}{k}. \)
The combination values \(\combinationalt{n}{k}\) as we vary \(n\) and \(k\) exhibit some patterns — see Figure 22.4.1 below.
\begin{gather*}
\combinationalt{0}{0} \\
\combinationalt{1}{0} \quad \combinationalt{1}{1} \\
\combinationalt{2}{0} \quad \combinationalt{2}{1} \quad \combinationalt{2}{2} \\
\combinationalt{3}{0} \quad \combinationalt{3}{1} \quad \combinationalt{3}{2} \quad \combinationalt{3}{3} \\
\combinationalt{4}{0} \quad \combinationalt{4}{1} \quad \combinationalt{4}{2} \quad
\combinationalt{4}{3} \quad \combinationalt{4}{4}\\
\combinationalt{5}{0} \quad \combinationalt{5}{1} \quad \combinationalt{5}{2} \quad
\combinationalt{5}{3} \quad \combinationalt{5}{4} \quad \combinationalt{5}{5}\\
\combinationalt{6}{0} \quad \combinationalt{6}{1} \quad \combinationalt{6}{2} \quad
\combinationalt{6}{3} \quad \combinationalt{6}{4} \quad \combinationalt{6}{5} \quad
\combinationalt{6}{6}\\
\vdots
\end{gather*}
\begin{equation*}
\longrightarrow
\end{equation*}
\begin{gather*}
1^{\phantom{0}}_{\phantom{0}} \\
1^{\phantom{1}}_{\phantom{0}} \quad 1^{\phantom{1}}_{\phantom{1}} \\
1^{\phantom{2}}_{\phantom{0}} \quad 2^{\phantom{2}}_{\phantom{1}} \quad 1^{\phantom{2}}_{\phantom{2}} \\
1^{\phantom{3}}_{\phantom{0}} \quad 3^{\phantom{3}}_{\phantom{1}} \quad 3^{\phantom{3}}_{\phantom{2}} \quad
1^{\phantom{3}}_{\phantom{3}}\\
1^{\phantom{4}}_{\phantom{0}} \quad 4^{\phantom{4}}_{\phantom{1}} \quad 6^{\phantom{4}}_{\phantom{2}} \quad
4^{\phantom{4}}_{\phantom{3}} \quad 1^{\phantom{4}}_{\phantom{4}}\\
1^{\phantom{5}}_{\phantom{0}} \quad 5^{\phantom{5}}_{\phantom{1}} \quad {10}^{\phantom{5}}_{\phantom{2}} \quad
{10}^{\phantom{5}}_{\phantom{0}} \quad 5^{\phantom{5}}_{\phantom{4}} \quad 1^{\phantom{5}}_{\phantom{5}}\\
1^{\phantom{6}}_{\phantom{0}} \quad 6^{\phantom{6}}_{\phantom{1}} \quad {15}^{\phantom{6}}_{\phantom{2}} \quad
{20}^{\phantom{6}}_{\phantom{3}} \quad {15}^{\phantom{6}}_{\phantom{4}} \quad 6^{\phantom{6}}_{\phantom{5}} \quad
1^{\phantom{6}}_{\phantom{6}}\\
\vdots
\end{gather*}
Studying the version of Pascal’s triangle involving the actual combination values, here are some of the patterns we observe.
- The values are symmetric about a vertical line through the centre of the triangle.
- It appears that every entry is the sum of the two entries immediately above.
- It appears that each row sums to a power of \(2\text{.}\)
We have already observed the first pattern as arising from the equivalence of choosing versus rejecting elements to form a subset (see Corollary 22.2.4 and Remark 22.2.5).
The next two propositions confirm that the other two observed patterns continue throughout the triangle.
Proof.
We could prove this equality just by comparing the factorial formulas involved on the left-hand and right-hand sides. But instead we will consider each of these combination values as representing the number of subsets of a certain size.
Write
\begin{equation*}
A = \natnumlt{n} = \{0,1,2,\dotsc,n - 1\}
\end{equation*}
so that \(\card{A} = n\text{.}\) Then the left-hand side of the equality in the statement of the proposition represents the number of subsets of \(A\) of size \(k\text{.}\) Let’s break that collection of subsets into two subcollections.
Subsets of \(A\) of size \(k\) that contain \(0\).
Each of these subsets will consist of \(0\) along with \(k - 1\) nonzero elements. As \(A\) contains \(n - 1\) nonzero elements from which to choose, there are \(\combinationalt{n - 1}{k - 1}\) ways to select those additional subset elements from \(A\text{.}\)
Subsets of \(A\) of size \(k\) that do not contain \(0\).
Each of these subsets must consist of \(k\) nonzero elements. As \(A\) contains \(n - 1\) nonzero elements from which to choose, there are \(\combinationalt{n - 1}{k}\) ways to select those subset elements from \(A\text{.}\)
Adding these two disjoint cases together using the Addition Rule yields the right-hand side of the equality.
Proposition 22.4.3.
For \(n\ge 0\text{,}\) we have \(\displaystyle \sum_{k=0}^n \combinationalt{n}{k} = 2^n\text{.}\)
Proof.
First, recall that the notation on the left-hand side is summation notation:
\begin{equation*}
\sum_{k=0}^n \combinationalt{n}{k} = \combinationalt{n}{0} + \combinationalt{n}{1} + \dotsb + \combinationalt{n}{n} \text{.}
\end{equation*}
Let \(A = \natnumlt{n}\text{,}\) so that \(\card{A} = n\text{.}\) Then \(\card{\powset{A}} = 2^n\) (Theorem 12.2.9). So the right-hand side of the equality represents the number of possible subsets of \(A\text{.}\)
On the other hand, for each index \(k\) in the sum on the left-hand side, the term \(\combinationalt{n}{k}\) is the number of subsets of \(A\) of size \(k\text{.}\) Using the Addition Rule, the sum of these terms must also be the total number of possible subsets of \(A\text{.}\)
Here is one further property of the choose function.
Proposition 22.4.4.
For \(0 \le m \le n\text{,}\) we have
\begin{equation*}
\combinationalt{n+1}{m+1} = \sum_{k=m}^n \combinationalt{k}{m} \text{.}
\end{equation*}
Proof.
Suppose \(A\) is a finite set with \(\card{A} = n + 1\text{.}\) (For example, we could use \(A = \natnumlt{n+1}\text{,}\) but that might get confusing between numbers as elements of \(A\) and numbers as cardinalities of subsets of \(A\text{.}\)) Then the left-hand side of the equality is the number of subsets of \(A\) of size \(m + 1\text{.}\) Here is a systematic way we could create that those subsets.
Choose an ordering of the elements of \(A\text{,}\) so that
\begin{equation*}
A = \{a_1,a_2,\dotsc,a_{n+1}\} \text{,}
\end{equation*}
though we will not count this choice of ordering. Then, proceed as follows.
- Write\begin{equation*} B_1 = \{a_1,a_2,\dotsc,a_{m+1}\}\text{,} \end{equation*}so that \(B_1 \subseteq A\) with \(\card{B_1} = m + 1\text{.}\) Then there is exactly \(1 = \combinationalt{m+1}{m+1}\) subset of \(B_1\) of size \(m + 1\text{,}\) which is \(B_1\) itself. And this subset of \(B_1\) is also a subset of \(A\text{.}\)
- Write\begin{equation*} B_2 = \{a_1,a_2,\dotsc,a_{m+1},a_{m+2}\}\text{,} \end{equation*}so that \(B_1 \subseteq B_2 \subseteq A\) with \(\card{B_2} = m + 2\text{.}\) Using only the elements of \(B_2\text{,}\) to create a new subset \(X \subseteq A\) of size \(m + 1\) that we have not already counted we must include the new element \(a_{m+2}\text{,}\) with the remaining \(m\) elements to make up \(X\) chosen from \(B_1\text{.}\) So we get \(\combinationalt{m+1}{m}\) new subsets of \(A\) of size \(m+1\) from \(B_2\text{.}\)
- Write\begin{equation*} B_3 = \{a_1,a_2,\dotsc,a_{m+1},a_{m+2},a_{m+3}\}\text{,} \end{equation*}so that \(B_2 \subseteq B_3 \subseteq A\) with \(\card{B_3} = m + 3\text{.}\) Using only the elements of \(B_3\text{,}\) to create a new subset of \(X \subseteq A\) of size \(m + 1\) that we have not already counted we must include the new element \(a_{m+3}\text{,}\) with the remaining \(m\) elements to make up \(X\) chosen from \(B_2\text{.}\) So we get \(\combinationalt{m+2}{m}\) new subsets of \(A\) of size \(m+1\) from \(B_3\text{.}\)
And so on. The last step in this process is when we create new subsets of size \(m+1\) by first choosing to include \(a_{n+1}\text{,}\) and then choosing the remaining \(m\) elements from \(A \smallsetminus \{a_{n+1}\}\text{,}\) giving us \(\combinationalt{n}{m}\) new subsets.
Every subset \(X \subseteq A\) of size \(m + 1\) is accounted for in the above process, since every such subset must contain at least one element with index \(m + 1\) or larger. If \(a_N\) is the element in \(X\) with the largest index, then \(X\) is one of the subsets considered in step \(\ell\text{,}\) where \(N = m + \ell\text{.}\)
So adding up each of these disjoint cases using the Addition Rule must yield the total number of subsets of \(A\) of size \(m + 1\text{.}\) Replacing the \(\combinationalt{m+1}{m+1}\) total from the first step with \(\combinationalt{m}{m}\) (since both are equal to \(1\)) to match the pattern of the subsequent steps, we obtain
\begin{equation*}
\combinationalt{n+1}{m+1} = \combinationalt{m}{m} + \combinationalt{m+1}{m} + \dotsb + \combinationalt{n}{m} \text{,}
\end{equation*}
as desired.
