Section6.4Pascal's triangle
Exercise 4.0.4 We prove that the two triangles are the same by induction. That is, we prove that the \(k\)th element of the \(n\)th row is the same in both triangles, and we prove this by induction on \(n\text{.}\) For \(n=0\) the two triangles have the same zero row: \(\binom{0}{0} = 1\text{.}\) Assume that the two triangles are equal in the \((n-1)\)st row. We prove that the two triangles contain the same numbers in the \(n\)th row, as well. The first and the last numbers are the same: \(\binom{n}{0} = 1\text{,}\) \(\binom{n}{n} = 1\text{.}\) Now, consider the \(k\)th element of the \(n\)th row for an arbitrary \(1\leq k\leq n-1\text{.}\) In Pascal's triangle it is the sum of the two numbers above it, that is, it is the sum of the \((k-1)\)st and the \(k\)th number of row \((n-1)\text{.}\) By the induction hypotheses, row \(n-1\) is the same in Pascal's triangle and in the triangle of the Binomial coefficients. That is, the \((k-1)\)st element of row \((n-1)\) is \(\binom{n-1}{k-1}\text{,}\) the \(k\)th element of row \((n-1)\) is \(\binom{n-1}{k}\text{.}\) By Proposition 4.0.3 we have \(\binom{n-1}{k-1}+ \binom{n-1}{k} = \binom{n}{k}\text{.}\) That is, the \(k\)th number of the \(n\)th row in Pascal's triangle is the same as the \(k\)th number of the \(n\)th row in the triangle of the Binomial coefficients. This is true for arbitrary \(1\leq k\leq n-1\text{,}\) thus the \(n\)th row of Pascal's triangle is the same as the \(n\)th row of the triangle of the binomial coefficients. This finishes the induction proof, the two triangles are the same.
Exercise 4.0.5 The first twelve rows of Pascal's triangle can be seen in Table 6.4.1 on page 6.4.1.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 Table6.4.1First twelve rows of Pascal's triangle. -
Exercise 4.1.2 The Binomial theorem holds for \(n=0\) and \(n=1\text{,}\) as well: \((x+y)^0 = 1 = \binom{0}{0} x^0 y^0\text{,}\) \((x+y)^1 = x + y = \binom{1}{0} x^1 y^0 + \binom{1}{1} x^0 y^1\text{.}\) Now, we can prove the theorem by induction on \(n\text{.}\) Assume that the statement holds for \(n-1\text{,}\) that is,
\begin{equation*} (x+y)^{n-1} = x^{n-1} + \binom{n-1}{1} x^{n-2}y + \dots + \binom{n-1}{1} xy^{n-2} + y^{n-1}\text{.} \end{equation*}This is the induction hypothesis. Now, compute \((x+y)^n\) using the same method as before, and use the induction hypothesis for expanding \((x+y)^{n-1}\text{:}\)
\begin{align*} (x+y)^n \amp = (x+y)^{n-1} \cdot (x+y)\\ \amp = \left( x^{n-1} + \binom{n-1}{1} x^{n-2}y + \dots + \binom{n-1}{n-2} xy^{n-2} + y^{n-1} \right) \cdot \left( x + y \right)\\ \amp = \left( x^{n-1} + \binom{n-1}{1} x^{n-2}y + \dots + \binom{n-1}{n-2} xy^{n-2} + y^{n-1} \right) \cdot x\\ \amp + \left( x^{n-1} + \binom{n-1}{1} x^{n-2}y + \dots + \binom{n-1}{n-2} xy^{n-2} + y^{n-1} \right) \cdot y\\ \amp = x^{n} + \binom{n-1}{1} x^{n-1}y + \dots + \binom{n-1}{n-2} x^2y^{n-2} + xy^{n-1}\\ \amp + x^{n-1}y + \binom{n-1}{1} x^{n-2}y^2 + \dots + \binom{n-1}{n-2} xy^{n-1} + y^{n}\\ \amp = x^{n} + \binom{n-1}{1} x^{n-1}y + \dots + \binom{n-1}{n-2} x^2y^{n-2} + \binom{n-1}{n-1} xy^{n-1}\\ \amp + \binom{n-1}{0} x^{n-1}y + \binom{n-1}{1} x^{n-2}y^2 + \dots + \binom{n-1}{n-2} xy^{n-1} + y^{n}\\ \amp = x^n + \left( \binom{n-1}{1} + \binom{n-1}{0} \right) x^{n-1}y + \dots\\ \amp \dots + \left( \binom{n-1}{k} + \binom{n-1}{k-1} \right) x^{n-k}y^k + \dots\\ \amp \dots + \left( \binom{n-1}{n-1} + \binom{n-1}{n-2} \right) xy^{n-1} + y^n\\ \amp = x^n + \binom{n}{1} x^{n-1}y + \dots + \binom{n}{k} x^{n-k}y^k + \dots + \binom{n}{n-1}xy^{n-1} + y^n\text{.} \end{align*}Here, we have expanded \((x+y)^{n-1}\) using the induction hypothesis, and multiplied it by \((x+y)\) by expanding the brackets. Then we collected together the same terms \(x^{n-k}y^k\) for every \(k=0, 1, \dots , n-1, n\text{.}\) Finally, in <<Unresolved xref, reference "eq_binomsum2"; check spelling or use "provisional" attribute>> we used the generating rule of Pascal's triangle (Proposition 4.0.3).
-
Exercise 4.1.3 Consider \((x+y)^n\text{:}\)
\begin{equation*} (x+y)^n = a_n x^n + a_{n-1}x^{n-1}y + a_{n-2}x^{n-2}y^2 + \dots + a_2x^2y^{n-2} + a_1xy^{n-1} + a_0y^n\text{,} \end{equation*}for some numbers \(a_n, a_{n-1}, \dots, a_1, a_0\text{.}\) How do we obtain the coefficient \(a_k\) for \(x^{n-k}y^k\text{?}\) Now, \((x+y)^n\) is the \(n\)-fold product of \((x+y)\) by itself:
\begin{equation*} (x+y)^n = \underbrace{(x+y) (x+y) \dots (x+y) (x+y)}_{n\text{ times } }\text{.} \end{equation*}The multiplication of these \(n\) factors is carried out by choosing a term from each factor (\(x\) or \(y\)) in every possible way, multiplying these \(n\) terms, and then adding the resulting products together. Thus the coefficient of \(x^{n-k}y^k\) is the number of possibilities to choose \((n-k)\)-times the \(x\) and \(k\)-times the \(y\) out of the \(n\) factors. Altogether there are \(n\) many \(y\)'s to choose from, and we need to choose \(k\) of them (and the remaining \((n-k)\) factors will be chosen as \(x\)). This can be done in \(\binom{n}{k}\)-many ways. Therefore the coefficient of \(x^{n-k}y^k\) is \(a_k=\binom{n}{k}\text{.}\)
- \begin{align*} 2^n \amp = (1+1)^n = 1^n + n \cdot 1^{n-1}\cdot 1 + \binom{n}{2} \cdot 1^{n-2}\cdot 1^2 + \dots + n \cdot 1 \cdot 1^{n-1} + 1^n\\ \amp = 1 + n + \binom{n}{2} + \dots + \binom{n}{k} + \dots + \binom{n}{n-2} + n + 1 = \sum_{k=0}^n \binom{n}{k}\text{.} \end{align*}
- \begin{align*} 0 \amp = 0^n = (1-1)^n\\ \amp = 1^n + n \cdot 1^{n-1}\cdot (-1) + \binom{n}{2} \cdot 1^{n-2}\cdot (-1)^2 + \dots + n \cdot 1 \cdot (-1)^{n-1} + (-1)^n\\ \amp = 1 - n + \binom{n}{2} - \dots + (-1)^{k} \binom{n}{k} + \dots + (-1)^{n-1} n + (-1)^n\\ \amp = \sum_{k=0}^n (-1)^k \binom{n}{k}\text{.} \end{align*}
-
Exercise 4.1.6 Using the Binomial theorem we obtain
\begin{align*} (x+y)^8\amp = \sum_{k=0}^8 \binom{8}{k} x^{8-k} y^k = x^8 + 8 x^7y + 28x^6y^2 + 56 x^5y^3\\ \amp + 70 x^4 y^4 + 56 x^3 y^5 + 28 x^2 y^6 + 8 x y^7 + y^8,\\ (x-y)^8\amp = \sum_{k=0}^8 \binom{8}{k} x^{8-k} \left( -y \right)^k = x^8 - 8 x^7y + 28x^6y^2 - 56 x^5y^3\\ \amp + 70 x^4 y^4 - 56 x^3 y^5 + 28 x^2 y^6 - 8 x y^7 + y^8,\\ (a+1)^{10} \amp = \sum_{k=0}^{10} \binom{10}{k} \cdot a^{10-k}\cdot 1^k = a^{10} + 10a^9 + 45a^8 + 120a^7\\ \amp + 210a^6 + 252a^5 + 210a^4 + 120 a^3 + 45 a^2 + 10a + 1,\\ (b-3)^5 \amp = \sum_{k=0}^5 \binom{5}{k} b^{5-k} \left( -3 \right)^k = b^5 -15 b^4 + 90 b^3\\ \amp -270 b^2 + 405 b - 243,\\ (1 + 2/x)^5 \amp = \sum_{k=0}^5 \binom{5}{k} \cdot 1^{5-k} \cdot \left( \frac{2}{x} \right)^k = 1 + \frac{10}{x} + \frac{40}{x^2} + \frac{80}{x^3} + \frac{80}{x^4} + \frac{32}{x^5},\\ \left( a + b \right)^6 \amp = \sum_{k=0}^6 \binom{6}{k} a^{6-k} b^k = a^6 + 6a^5b + 15 a^4 b^2 + 20 a^3 b^3\\ \amp + 15 a^2 b^4 + 6ab^5 + b^6,\\ \left( 1 + x \right)^5 \amp = \sum_{k=0}^5 \binom{5}{k} \cdot 1^{5-k} \cdot x^k = 1 + 5x + 10x^2\\ \amp + 10x^3 + 5x^4 + x^5,\\ \left(3a + 4b \right)^4 \amp = \sum_{k=0}^4 \binom{4}{k} \cdot \left(3a\right)^{4-k} \cdot \left(4b\right)^k = \left( 3a \right)^4 + 4 \cdot \left( 3a \right)^3 \cdot \left( 4b \right)\\ \amp + 6 \cdot \left( 3a \right)^2 \cdot \left( 4b \right)^2 + 4 \cdot \left( 3a \right) \cdot \left( 4b \right)^3 + \left( 4b \right)^4 = 81 a^4\\ \amp + 432 a^3b + 864 a^2b^2 + 768 ab^3 + 256 b^4,\\ \left( 3 - 2x \right)^4 \amp = \sum_{k=0}^4 \binom{4}{k} \cdot 3^{4-k} \cdot \left(-2x\right)^k = 3^4 - 4 \cdot 3^3 \cdot \left( 2x \right) + 6 \cdot 3^2 \cdot \left( 2x \right)^2\\ \amp - 4 \cdot 3 \cdot \left( 2x \right)^3 + \left( 2x \right)^4 = 81 - 216 x + 216 x^2 - 96 x^3 + 16 x^4\text{.} \end{align*} -
Exercise 4.1.7 By the Binomial theorem
\begin{equation*} \left( 1-\frac{x}{2} \right)^9 = \sum_{k=0}^9 \binom{9}{k} \cdot 1^{9-k} \cdot \left( - \frac{x}{2} \right)^k = \sum_{k=0}^9 \left( -1 \right)^k \cdot \frac{\binom{9}{k}}{2^k} \cdot x^k\text{.} \end{equation*}Here, the fourth term corresponds to \(x^3\text{,}\) that is, \(\left( -1 \right)^3 \cdot \binom{9}{3}/2^3 x^3 = - 84/8 x^3 = -21/2 x^3 = -10.5 x^3\text{.}\) The coefficient of \(x^5\) is \(\left( -1 \right)^5 \cdot \binom{9}{5}/2^5 = - 126/32 = -63/16 = -3.9375\text{.}\)
Exercise 4.2.1 If \(n\) is odd, then every binomial coefficient occurs twice in the sum: once with positive sign, and once with negative sign. Indeed, the sign of \(\binom{n}{k}\) is \((-1)^k\) and the sign of \(\binom{n}{n-k}\) is \((-1)^{n-k}\text{.}\) They cannot have the same sign, because their product is \((-1)^k \cdot (-1)^{n-k} = (-1)^n = -1\text{,}\) as \(n\) is odd. Thus every binomial coefficient occurs twice with different signs, their sum is 0, and the whole sum is 0, as well.
-
Exercise 4.2.2 Consider the alternating sum of the \(n\)th row (for \(n\geq 1\)), and use the generating rule of Pascal's triangle: {
\begin{align*} \amp \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dots + (-1)^{n-1} \cdot \binom{n}{n-1} + (-1)^{n} \cdot \binom{n}{n}\\ \amp = \binom{n-1}{0} - \left( \binom{n-1}{0} + \binom{n-1}{1} \right) + \left( \binom{n-1}{1} + \binom{n-1}{2} \right) - \dots\\ \amp + (-1)^{n-1} \cdot \left( \binom{n-1}{n-2} + \binom{n-1}{n-1} \right) + (-1)^{n} \cdot \binom{n-1}{n-1}\\ \amp = \left( \binom{n-1}{0} - \binom{n-1}{0} \right) + \left( - \binom{n-1}{1} + \binom{n-1}{1} \right) +\\ \amp +\left( \binom{n-1}{2} - \binom{n-1}{2} \right) + \dots + \left( \left( -1 \right)^{n-2} \cdot \binom{n-1}{n-2} + \left( -1 \right)^{n-1} \cdot \binom{n-1}{n-2} \right)\\ \amp + \left( \left( -1 \right)^{n-1} \cdot \binom{n-1}{n-1} + \left( -1 \right)^{n} \cdot \binom{n-1}{n-1} \right)\\ \amp = 0 + 0 + 0 + \dots + 0 + 0 = 0\text{.} \end{align*}} First, we replaced \(\binom{n}{0}=1\) by \(\binom{n-1}{0}=1\text{,}\) and \(\binom{n}{n} = 1\) by \(\binom{n-1}{n-1} = 1\text{,}\) then we used the generating rule of Pascal's triangle. Then we observed that every \(\binom{n-1}{k}\) occurs twice in the sum: first with a positive sign, then right after it with a negative sign (for \(0\leq k\leq n-1\)).
-
Exercise 4.2.5 Again, we give a combinatorial meaning to both sides of <<Unresolved xref, reference "eq_n_mchoosek"; check spelling or use "provisional" attribute>> . The right hand side gives a clue: \(\binom{n+m}{l}\) is the number of ways to choose \(l\) elements out of an \((n+m)\)-element set, say
\begin{equation*} S = \halmaz{1, 2, \dots , n, n+1, n+2, \dots , n+m}\text{.} \end{equation*}Our plan is to prove that the left hand side of <<Unresolved xref, reference "eq_n_mchoosek"; check spelling or use "provisional" attribute>> is the number of \(l\)-element subsets of \(S\text{,}\) as well. Let \(S_1 = \halmaz{1, 2, \dots , n}\) and \(S_2 = \halmaz{n+1, n+2, \dots , n+m}\text{.}\) Now, try to count the number of ways to choose \(l\) elements of \(S\) by counting how many elements we choose from \(S_1\) and from \(S_2\text{.}\) If we choose 0 element from \(S_1\text{,}\) then we must choose \(l\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{0} \cdot \binom{m}{l}\)-many ways. If we choose 1 element from \(S_1\text{,}\) then we must choose \(l-1\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{1} \cdot \binom{m}{l-1}\)-many ways. If we choose 2 elements from \(S_1\text{,}\) then we must choose \(l-2\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{2} \cdot \binom{m}{l-2}\)-many ways. In general, if we choose k elements from \(S_1\text{,}\) then we must choose \(l-k\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{k} \cdot \binom{m}{l-k}\)-many ways. In the end, if we choose \(l\) elements from \(S_1\text{,}\) then we must choose \(0\) element from \(S_2\text{.}\) We can do this in \(\binom{n}{l} \cdot \binom{m}{0}\)-many ways. Thus, choosing \(l\) elements out of \(n+m\) can be done in the following number of ways:
\begin{equation*} \binom{n}{0} \cdot \binom{m}{l} + \binom{n}{1} \cdot \binom{m}{l-1} + \dots + \binom{n}{l}\cdot \binom{m}{0} = \sum_{k=0}^l \binom{n}{k} \cdot \binom{m}{l-k}\text{.} \end{equation*}That is, both sides of <<Unresolved xref, reference "eq_n_mchoosek"; check spelling or use "provisional" attribute>> counts the number of ways of choosing \(l\) elements out of an \((n+m)\)-element set, and therefore must be equal. If we choose \(n=m=l\text{,}\) and use the symmetry of Pascal's triangle \(\binom{n}{k} = \binom{n}{n-k}\text{,}\) then we obtain exactly equation (4.2.2).
-
Exercise 4.2.6 Consider \((x+y)^{n+m}\text{,}\) and expand it using the Binomial theorem:
\begin{equation*} (x+y)^{n+m} = \sum_{k=0}^{n+m} \binom{n+m}{k} x^{n+m-k} \cdot y^{k}\text{.} \end{equation*}Then the right hand side of <<Unresolved xref, reference "eq_n_mchoosek"; check spelling or use "provisional" attribute>> is the coefficient of the term \(x^{n+m-l}y^l\text{.}\) We prove that the left hand side is the coefficient of \(x^{n+m-l}y^l\text{,}\) as well. For this, we compute \((x+y)^{n+m}\) by multiplying \((x+y)^n \cdot (x+y)^m\) after expanding both factors using the Binomial theorem:
\begin{equation*} (x+y)^{n+m} = (x+y)^n \cdot (x+y)^m = \left( \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k \right) \cdot \left( \sum_{k=0}^m \binom{m}{k} x^{m-k}y^k \right)\text{.} \end{equation*}Now, let us compute the coefficient of \(x^{n+m-l} y^l\text{.}\) When do we obtain \(x^{n+m-l} y^l\) when we multiply \(\left( \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k \right)\) by \(\left( \sum_{k=0}^m \binom{m}{k} x^{m-k}y^k \right)\text{?}\) For some \(0\leq k\leq l\) the term \(x^{n-k}y^k\) in the first factor must be multiplied by \(x^{m-l+k} y^{l-k}\) from the second factor. The coefficient of \(x^{n-k}y^k\) in the first factor is \(\binom{n}{k}\text{,}\) the coefficient of \(x^{m-l+k}y^{l-k}\) in the second factor is \(\binom{m}{l-k}\text{,}\) thus this multiplication contributes by \(\binom{n}{k} \cdot \binom{m}{l-k}\) to the coefficient of \(x^{n+m-l} y^l\) in \((x+y)^{n+m}\text{.}\) That is, the coefficient of \(x^{n+m-l} y^l\) in \((x+y)^{n+m}\) is
\begin{equation*} \sum_{k=0}^l \binom{n}{k} \cdot \binom{m}{l-k}\text{.} \end{equation*}Moreover, the coefficient of \(x^{n+m-l}y^l\) in \((x+y)^{n+m}\) is \(\binom{n+m}{l}\text{,}\) thus the two numbers must be equal, which proves <<Unresolved xref, reference "eq_n_mchoosek"; check spelling or use "provisional" attribute>> :
\begin{equation*} \sum_{k=0}^n \binom{n}{k} \cdot \binom{m}{l-k} = \binom{n+m}{l}\text{.} \end{equation*} -
Exercise 4.2.8 We can try to prove the identity by induction on \(m\text{.}\) For \(m=0\) the identity holds, as the left hand side is \(\binom{n}{0} = 1\text{,}\) the right hand side is \(\binom{n+1}{0} = 1\text{,}\) as well. Assume that the identity holds for \(m-1\text{,}\) that is,
\begin{equation*} \sum_{k=0}^{m-1} \binom{n+k}{k} = \binom{n}{0} + \binom{n+1}{1} + \dots + \binom{n+m-1}{m-1} = \binom{n+m}{m-1}\text{.} \end{equation*}This is the induction hypothesis. Now we prove the identity for \(m\text{.}\)
\begin{align*} \amp \sum_{k=0}^{m} \binom{n+k}{k} = \underbrace{\binom{n}{0} + \binom{n+1}{1} + \dots + \binom{n+m-1}{m-1}}_{= \binom{n+m}{m-1}, \text{ by the induction hypothesis } } + \binom{n+m}{m}\\ \amp = \binom{n+m}{m-1} + \binom{n+m}{m} = \binom{n+m+1}{m}\text{.} \end{align*}Here, we first used the induction hypothesis, then the generating rule of Pascal's triangle (Proposition 4.0.3). We can spare ourselves an induction proof if we use \(\binom{n+k}{k} = \binom{n+k}{n}\text{.}\) That is,
\begin{align*} \amp \sum_{k=0}^{m} \binom{n+k}{k} = \binom{n}{0} + \binom{n+1}{1} + \dots + \binom{n+m}{m}\\ \amp = \binom{n}{n} + \binom{n+1}{n} + \dots + \binom{n+m-1}{n} = \sum_{k=n}^{n+m} \binom{k}{n}\\ \amp = \binom{n+m+1}{n+1} = \binom{n+m+1}{m} \end{align*} -
Exercise 4.2.9 The \(k\)th element of row \(p\) is
\begin{equation*} \binom{p}{k} = \frac{p!}{k!\cdot (p-k)!}\text{.} \end{equation*}This number is an integer number, the nominator is divisible by the prime \(p\text{.}\) However, for \(1\leq k\leq p-1\text{,}\) the denominator only contains positive integers strictly less than \(p\text{.}\) Thus, when we simplify this fraction for obtaining the resulting integer, the factor \(p\) in the nominator will not cancel out with anything in the denominator, and thus \(p\) will divide the integer \(\binom{p}{k}\text{.}\) If \(p\) is not a prime, then this property does not necessarily hold. For example if \(n\) is even then by Exercise 2.6.10 we have \(n \nmid \binom{n}{2}\text{.}\) Furthermore, in the first 12 rows we have
\begin{align*} 6 \amp \nmid \binom{6}{3} = 20,\\ \amp \amp 8 \amp \nmid \binom{8}{4} = 70,\\ 9 \amp \nmid \binom{9}{3} = 84,\\ \amp \amp \amp \amp 10 \amp \nmid \binom{10}{5} = 252,\\ 12 \amp \nmid \binom{12}{3} = 220, \amp 12 \amp \nmid \binom{12}{4} = 495\text{.} \end{align*}