Skip to main content
\(\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{ #1}}{\thechapter~ #1}} \renewcommand{\sectionmark}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \renewcommand{\theenumi}{5.\arabic{enumi}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\norma}[1]{\left\|#1\right\|} \newcommand{\BM}[1]{\text{\boldmath$#1$}} \newcommand{\halmaz}[1]{\left\{\,#1\,\right\}} \newcommand{\halmazvonal}[2]{\left\{\,#1\mid #2\,\right\}} \newcommand{\halmazpont}[2]{\left\{\,#1:#2\,\right\}} \newcommand{\N}{\mathbb{N}} \newcommand{\len}{\norm} \newcommand{\var}[2][]{v_{#1}\left(#2\right)} \newcommand{\vari}[2]{v_{#1}\left(#2\right)} \newcommand{\size}[2][]{s_{#1}\left(#2\right)} \newcommand{\dep}[2][]{d_{#1}\left(#2\right)} \newcommand{\sizestar}[2][]{s_{#1}^*\left(#2\right)} \newcommand{\depstar}[2][]{d_{#1}^*\left(#2\right)} \renewcommand{\headrulewidth}{0pt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Chapter4Pascal's triangle

Let us create a triangle from numbers in the following way. Let us write 1 to the top. This we call row zero of the triangle. Then every row of the triangle contains one more numbers than the row before, aligned in a way that every number is lower left and/or lower right from the numbers in the row above. We start and end every row by 1, and in between we write numbers which are the sums of the two numbers above them, that is, we write the sum of the upper left and upper right numbers. Thus in the first row (right below the top 1) we write 1 to lower left and to lower right of this number. Then in the second row we write 1, 2, 1, such that 2 is in between the two 1's of the first row. In the third row, we write 1, 3, 3, 1, etc. (see Table 4.0.1). This way, one can easily compute the numbers occurring in the triangle row after row. This triangle is called Pascal's triangle, named after the French polymath Blaise Pascal (1623–1662).

1
\noalign 1 1
\noalign 1 2 1
\noalign 1 3 3 1
\noalign 1 4 6 4 1
\noalign 1 5 10 10 5 1
\noalign 1 6 15 20 15 6 1
\noalign
Table4.0.1Pascal's triangle.

Let us now take a closer look to these numbers. Consider for example the sixth row: 1, 6, 15, 20, 15, 6, 1. They look like the binomial coefficients \(\binom{6}{k}\text{.}\) Indeed, \(1 = \binom{6}{0}\text{,}\) \(6 = \binom{6}{1}\text{,}\) \(15 = \binom{6}{2}\text{,}\) \(20 = \binom{6}{3}\text{,}\) \(15 = \binom{6}{4}\text{,}\) \(6 = \binom{6}{5}\text{,}\) \(1 = \binom{6}{6}\text{.}\) It seems that (at least for this small part of the triangle), in the \(n\)th row the binomial coefficients \(\binom{n}{k}\) occur for \(k=0, 1, 2, \dots , n\text{.}\) This is true for the first row (\(\binom{1}{0}=1\text{,}\) \(\binom{1}{1}=1\)), and even for the zero row: \(\binom{0}{0}=1\text{.}\) That is, it looks like Pascal's triangle is the same as the triangle of the binomial coefficients, where in the \(n\)th row we write the binomial coefficients \(\binom{n}{0}\text{,}\) \(\binom{n}{1}\text{,}\) \(\binom{n}{2}\text{,}\) \(\dots\text{,}\) \(\binom{n}{n}\) such that we align the midpoints of the rows (Table 4.0.2).

\(\binom{0}{0}\)
\noalign \(\binom{1}{0}\) \(\binom{1}{1}\)
\noalign \(\binom{2}{0}\) \(\binom{2}{1}\) \(\binom{2}{2}\)
\noalign \(\binom{3}{0}\) \(\binom{3}{1}\) \(\binom{3}{2}\) \(\binom{3}{3}\)
\noalign \(\binom{4}{0}\) \(\binom{4}{1}\) \(\binom{4}{2}\) \(\binom{4}{3}\) \(\binom{4}{4}\)
\noalign \(\binom{5}{0}\) \(\binom{5}{1}\) \(\binom{5}{2}\) \(\binom{5}{3}\) \(\binom{5}{4}\) \(\binom{5}{5}\)
\noalign \(\binom{6}{0}\) \(\binom{6}{1}\) \(\binom{6}{2}\) \(\binom{6}{3}\) \(\binom{6}{4}\) \(\binom{6}{5}\) \(\binom{6}{6}\)
\noalign
Table4.0.2Triangle of Binomial coefficients.

How can we prove that the two triangles are one and the same? One way to do it would be to prove that they can be generated by the same rule. Pascal's triangle was generated such that every row starts and ends with 1, and every other number is the sum of the two numbers right above it. Considering the \(n\)th row in Table 4.0.2, it starts by \(\binom{n}{0}=1\text{,}\) and it ends with \(\binom{n}{n} = 1\text{.}\) Thus we only need to check whether every other number is the sum of the two numbers above it. The \(k\)th number in the \(n\)th row is \(\binom{n}{k}\) (every row starts with the zeroth number), the two numbers above it are the \((k-1)\)st and \(k\)th of row \(n-1\text{,}\) that is, \(\binom{n-1}{k-1}\) and \(\binom{n-1}{k}\text{.}\) Thus, if we prove that \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{,}\) then the two triangles are indeed the same.

Let us substitute the formula (2.6.1) into the right-hand side:

\begin{align*} \amp { } \binom{n-1}{k-1} + \binom{n-1}{k}\\ \amp = \frac{(n-1)!}{(k-1)! \cdot (n-1-(k-1))!} + \frac{(n-1)!}{k! \cdot (n-1-k)!}\\ \amp = \frac{(n-1)!}{(k-1)! \cdot (n-k)!} + \frac{(n-1)!}{k! \cdot (n-k-1)!}\\ \amp = \frac{(n-1)!\cdot k + (n-1)! \cdot (n-k)}{k! \cdot (n-k)!} = \frac{(n-1)!\cdot (k + n-k)}{k! \cdot (n-k)!}\\ \amp = \frac{(n-1)!\cdot n}{k! \cdot (n-k)!} = \frac{n!}{k! \cdot (n-k)!} = \binom{n}{k}\text{.} \end{align*}

Create a precise proof using induction that the two triangles are the same.

This proof is a correct one, but not necessarily satisfying. It contains calculations, but does not show the reason why the sum of the binomial coefficients \(\binom{n-1}{k-1}\) and \(\binom{n-1}{k}\) is really \(\binom{n}{k}\text{.}\) One might wonder if there is an “easier” proof, which only uses the definition of \(\binom{n}{k}\text{.}\) Indeed there is, as we show now.

Let \(A=\halmaz{1, 2, \dots , n}\text{,}\) and we count the number of \(k\)-element subsets of \(A\) in two different ways. On the one hand, we know that the number of \(k\)-element subsets of \(A\) is \(\binom{n}{k}\text{.}\) On the other hand, we count the \(k\)-element subsets such that we first count those which contain the element \(n\text{,}\) then we count those, which do not.

Count the number of \(k\)-element subsets of \(A\) containing \(n\) first. If a \(k\)-element subset \(S\) of \(A\) contains \(n\text{,}\) then it contains \(k-1\) more elements from \(\halmaz{1, 2, \dots , n-1}\text{.}\) Such a subset can be chosen in \(\binom{n-1}{k-1}\)-many ways. Thus, \(A\) has \(\binom{n-1}{k-1}\)-many \(k\)-element subsets containing the element \(n\text{.}\)

Now, count the number of \(k\)-element subsets of \(A\) not containing \(n\text{.}\) If a \(k\)-element subset \(S\) of \(A\) does not contain \(n\text{,}\) then it contains \(k\) elements from \(\halmaz{1, 2, \dots , n-1}\text{.}\) Such a subset can be chosen in \(\binom{n-1}{k}\)-many ways. Thus, \(A\) has \(\binom{n-1}{k}\)-many \(k\)-element subsets not containing the element \(n\text{.}\) As a \(k\)-element subset either contains or does not contain the element \(n\text{,}\) the number of \(k\)-element subsets of \(A\) is \(\binom{n-1}{k-1} + \binom{n-1}{k}\text{,}\) which therefore must be the same number as \(\binom{n}{k}\text{.}\)

Compute the first twelve rows of Pascal's triangle.