Section4.2Identities
In this Section we investigate several properties of Pascal's triangle. Throughout this Section, we will first conjecture what identities hold by looking at the first 12 rows of Pascal's triangle. Therefore solving Exercise 4.0.5 is essential before continuing.
Let us start by the sum of the numbers in a row:
\begin{align*} 1 \amp = 1,\\ 1 + 1 \amp = 2,\\ 1 + 2 + 1 \amp = 4,\\ 1 + 3 + 3 + 1 \amp = 8,\\ 1 + 4 + 6 + 4 + 1 \amp = 16,\\ 1 + 5 + 10 + 10 + 5 + 1 \amp = 32,\\ 1 + 6 + 15 + 20 + 15 + 6 + 1 \amp = 64\text{.} \end{align*}It seems from these equations that the sum of the numbers in the \(n\)th row is \(2^n\text{.}\) This stetement is equivalent to the equality
\begin{equation} \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n-2} + \binom{n}{n-1} + \binom{n}{n} = 2^n\text{.}\tag{4.2.1} \end{equation}Note, that we have already proved this, first in Proposition 2.6.9, then later in Exercise 4.1.4. Now, we prove it a third way, using the generating rule of Pascal's triangle.
Let us consider first the 7th row, and try to compute the sum using the generating rule of Pascal's triangle, rather than adding the numbers:
\begin{align*} \amp 1 + 7 + 21 + 35 + 35 + 21 + 7 + 1\\ \amp = 1 + (1 + 6) + (6 + 15) + (15 + 20) + (20 + 15) + (15 + 6) + (6 + 1) + 1\\ \amp = 2 \cdot (1 + 6 + 15 + 20 + 15 + 6 + 1 ) = 2 \cdot 2^6 = 2^7 = 128\text{.} \end{align*}This idea can be used in the general case, as well.
Now, we prove that the sum of the numbers in the \(n\)th row of Pascal's triangle is \(2^n\) by induction on \(n\text{.}\) The statement holds for \(n=0\) and \(n=1\) (in fact, we just calculated that it holds for \(n\leq 7\)). Assume now that the statement holds for \(n\text{,}\) as well. That is, the sum of the numbers in the \(n\)th row is \(2^{n}\text{.}\) Consider the sum of the \((n+1)\)st row, and let us use the generating rule of Pascal's triangle:
\begin{align*} \amp \binom{n+1}{0} + \binom{n+1}{1} + \binom{n+1}{2} + \dots + \binom{n+1}{n-1} + \binom{n+1}{n} + \binom{n+1}{n+1}\\ \amp = \binom{n}{0} + \left( \binom{n}{0} + \binom{n}{1} \right) + \left( \binom{n}{1} + \binom{n}{2} \right) + \left( \binom{n}{2} + \binom{n}{3} \right) + \dots\\ \amp + \left( \binom{n}{n-2} + \binom{n}{n-1} \right) + \left( \binom{n}{n-1} + \binom{n}{n} \right) + \binom{n}{n}\\ \amp = 2 \cdot \left[ \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n-2} + \binom{n}{n-1} + \binom{n}{n} \right]\\ \amp = 2 \cdot 2^{n} = 2^{n+1}\text{.} \end{align*}First, we replaced \(\binom{n+1}{0}=1\) by \(\binom{n}{0}=1\text{,}\) and \(\binom{n+1}{n+1} = 1\) by \(\binom{n}{n} = 1\text{,}\) then we used the generating rule of Pascal's triangle. Then we observed that every \(\binom{n}{k}\) occurs twice in the sum (for \(0\leq k\leq n\)). Finally, we used the induction hypothesis on the sum of the numbers for the \(n\)th row.
Let us use a similar reasoning to calculate the sum of the numbers in a row, with alternating signs. That is, compute the sum
\begin{equation*} \sum_{k=0}^n \left( -1 \right)^k \cdot \binom{n}{k} = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dots + \left( -1 \right)^{n-1} \cdot \binom{n}{n-1} + \left( -1 \right)^{n} \cdot \binom{n}{n}\text{.} \end{equation*}It is easy to compute this sum for the first couple rows:
\begin{align*} 1 \amp = 1,\\ 1 - 1 \amp = 0,\\ 1 - 2 + 1 \amp = 0,\\ 1 - 3 + 3 - 1 \amp = 0,\\ 1 - 4 + 6 - 4 + 1 \amp = 0,\\ 1 - 5 + 10 - 10 + 5 - 1 \amp = 0,\\ 1 - 6 + 15 - 20 + 15 - 6 + 1 \amp = 0,\\ 1 - 7 + 21 - 35 + 35 - 21 + 7 - 1 \amp = 0\text{.} \end{align*}It seems likely that for \(n\geq 1\) the alternating sum of the numbers in the \(n\)th row of Pascal's triangle is 0.
The alternating sum of the \(n\)th row is clearly 0 if \(n\) is odd. Why?
Let us try to use the former argument to compute the alternating sum of the numbers in the 8th row:
\begin{align*} \amp 1 - 8 + 28 - 56 + 70 - 56 + 28 - 8 + 1 = 1 - (1 + 7) + (7 + 21) - (21 + 35)\\ \amp + (35 + 35) - (35 + 21) + (21+7) - (7 + 1) + 1 = (1-1) + (-7+7)\\ \amp + (21-21) + (-35 + 35) + (35-35) + (-21 + 21) + (7-7) + (-1+1) = 0\text{.} \end{align*}Using the very same proof technique, we can prove that the alternating sum is 0 in the \(n\)th row, as well.
Exercise4.2.2
Prove that the alternating sum of the \(n\)th row is 0, that is,
\begin{equation*} \sum_{k=0}^n \left( -1 \right)^k \cdot \binom{n}{k} = \binom{n}{0} - \binom{n}{1} + \dots + \left( -1 \right)^{n-1} \cdot \binom{n}{n-1} + \left( -1 \right)^{n} \cdot \binom{n}{n} = 0\text{.} \end{equation*}In fact, the technique can be used to prove an even more general statement, namely we can determine the alternating sum if we stop at the \(k\)th term (for some \(k\leq n-1\)):
Proposition4.2.3
\begin{equation*} \binom{n}{0} - \binom{n}{1} + \dots + \left( -1 \right)^{k-1} \cdot \binom{n}{k-1} + \left( -1 \right)^{k} \cdot \binom{n}{k} = \left( - 1 \right)^k \cdot \binom{n-1}{k}\text{.} \end{equation*}Proof
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 + \left( -1 \right)^{k-1} \cdot \binom{n}{k-1} + \left( -1 \right)^{k} \cdot \binom{n}{k}\\ \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)^{k-1} \cdot \left( \binom{n-1}{k-2} + \binom{n-1}{k-1} \right) + (-1)^{k} \cdot \left( \binom{n-1}{k-1} + \binom{n-1}{k} \right)\\ \amp = \left( \binom{n-1}{0} - \binom{n-1}{0} \right) + \left( - \binom{n-1}{1} + \binom{n-1}{1} \right) + \left( \binom{n-1}{2} - \binom{n-1}{2} \right) + \dots\\ \amp + \left( \left( -1 \right)^{k-2} \cdot \binom{n-1}{k-2} + \left( -1 \right)^{k-1} \cdot \binom{n-1}{k-2} \right)\\ \amp + \left( \left( -1 \right)^{k-1} \cdot \binom{n-1}{k-1} + \left( -1 \right)^{k} \cdot \binom{n-1}{k-1} \right) + \left( -1 \right)^k \cdot \binom{n-1}{k}\\ \amp = 0 + 0 + 0 + \dots + 0 + 0 + \left( -1 \right)^k \cdot \binom{n-1}{k} = \left( -1 \right)^k \cdot \binom{n-1}{k}\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}{j}\) occurs twice in the sum: first with a positive sign, then right after it with a negative sign (for \(0\leq j\leq k-1\)). The only term remaining is \(\left( -1 \right)^k \cdot \binom{n-1}{k}\text{.}\)
If we define \(\binom{n-1}{n}\) to be 0 (considering there are no \(n\)-element subsets of an \((n-1)\)-element set), then our statement on the alternating sums follows from Proposition 4.2.3.
Now, consider the sum of the squares of the numbers in a row. We can find a pattern here, as well:
\begin{align*} 1^2 \amp = 1,\\ 1^2 + 1^2 \amp = 2,\\ 1^2 + 2^2 + 1^2 \amp = 6,\\ 1^2 + 3^2 + 3^2 + 1^2 \amp = 20,\\ 1^2 + 4^2 + 6^2 + 4^2 + 1^2 \amp = 70,\\ 1^2 + 5^2 + 10^2 + 10^2 + 5^2 + 1^2 \amp = 252,\\ 1^2 + 6^2 + 15^2 + 20^2 + 15^2 + 6^2 + 1^2 \amp = 924\text{.} \end{align*}After computing the first twelve rows of Pascal's triangle in Exercise 4.0.5, we can observe that the results are the numbers occurring in the middle column. That is, we can conjecture that the sum of the square of the numbers in row \(n\) is \(\binom{2n}{n}\text{,}\) that is,
Proposition4.2.4
\begin{equation} \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{n}{0}^2 + \binom{n}{1}^2 + \dots + \binom{n}{n-1}^2 + \binom{n}{n}^2 = \binom{2n}{n}\text{.}\label{eq_sumsquaresofrow}\tag{4.2.2} \end{equation}Proof
As earlier, we try to understand why this equation holds by giving a combinatorial meaning to both sides. The right hand side gives away a clue: \(\binom{2n}{n}\) is the number of ways to choose \(n\) elements out of a \(2n\)-element set (say \(S = \halmaz{1, 2, \dots , 2n}\)). Our plan is to prove that the left hand side of (4.2.2) is the number of \(n\)-element subsets of \(S\text{,}\) as well. Let \(S_1 = \halmaz{1, 2, \dots , n}\) and \(S_2 = \halmaz{n+1, n+2, \dots , 2n}\text{.}\) Now, try to count the number of ways to choose \(n\)-element 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 \(n\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{0} \cdot \binom{n}{n}\)-many ways. If we choose 1 element from \(S_1\text{,}\) then we must choose \(n-1\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{1} \cdot \binom{n}{n-1}\)-many ways. If we choose 2 elements from \(S_1\text{,}\) then we must choose \(n-2\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{2} \cdot \binom{n}{n-2}\)-many ways. In general, if we choose k elements from \(S_1\text{,}\) then we must choose \(n-k\) elements from \(S_2\text{.}\) We can do this in \(\binom{n}{k} \cdot \binom{n}{n-k}\)-many ways. In the end, if we choose \(n\) elements from \(S_1\text{,}\) then we must choose \(0\) element from \(S_2\text{.}\) We can do this in \(\binom{n}{n} \cdot \binom{n}{0}\)-many ways. Thus, choosing \(n\) elements out of \(2n\) can be done in the following number of ways:
\begin{equation*} \binom{n}{0} \cdot \binom{n}{n} + \binom{n}{1} \cdot \binom{n}{n-1} + \dots + \binom{n}{n}\cdot \binom{n}{0} = \sum_{k=0}^n \binom{n}{k} \cdot \binom{n}{n-k}\text{.} \end{equation*}Finally, let us rewrite the left hand side by using the symmetry of Pascal's triangle, that is, \(\binom{n}{n-k} = \binom{n}{k}\) to obtain the left hand side of (4.2.2):
\begin{align*} \amp \binom{n}{0} \cdot \binom{n}{n} + \binom{n}{1} \cdot \binom{n}{n-1} + \dots + \binom{n}{n}\cdot \binom{n}{0} = \sum_{k=0}^n \binom{n}{k} \cdot \binom{n}{n-k}\\ \amp = \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{n}{0}^2 + \binom{n}{1}^2 + \dots + \binom{n}{n-1}^2 + \binom{n}{n}^2\text{.} \end{align*}That is, both sides of (4.2.2) counts the number of ways of choosing \(n\) elements out of a \(2n\)-element set (or alternatively, the number of \(n\)-element subsets of a \(2n\)-element set), and therefore must be equal.
This idea can be used in a more general setting.
Exercise4.2.5
Prove that
\begin{align*} \amp \sum_{k=0}^l \binom{n}{k} \cdot \binom{m}{l-k} = \binom{n+m}{l}, \text{ that is, }\\ \amp \binom{n}{0} \cdot \binom{m}{l} + \binom{n}{1} \cdot \binom{m}{l-1} + \dots + \binom{n}{l} \cdot \binom{m}{0}= \binom{n+m}{l}\text{.} \end{align*}How do we need to choose \(m\) and \(l\) so that <<Unresolved xref, reference "eq_n_mchoosek"; check spelling or use "provisional" attribute>> gives us the equality (4.2.2)?
We could have used the Binomial theorem to prove (4.2.2):
Proof
Consider \((x+y)^{2n}\text{,}\) and expand it using the Binomial theorem:
\begin{equation*} (x+y)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} x^{2n-k} \cdot y^{k}\text{.} \end{equation*}Then the right hand side of (4.2.2) is the coefficient of the term \(x^ny^n\text{.}\) We prove that the left hand side is the coefficient of \(x^ny^n\text{,}\) as well. For this, we compute \((x+y)^{2n}\) by multiplying \((x+y)^n \cdot (x+y)^n\) after expanding both factors using the Binomial theorem:
\begin{equation*} (x+y)^{2n} = (x+y)^n \cdot (x+y)^n = \left( \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k \right) \cdot \left( \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k \right)\text{.} \end{equation*}Now, let us compute the coefficient of \(x^n y^n\text{.}\) When do we obtain \(x^n y^n\) when we multiply \(\left( \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k \right)\) by itself? Take for example \(x^n\) from the first factor, this must be multiplied by \(y^n\) from the second factor to obtain \(x^n y^n\text{.}\) The coefficient of \(x^n\) in the first factor is \(\binom{n}{0}\text{,}\) the coefficient of \(y^n\) in the second factor is \(\binom{n}{n}\text{,}\) thus this multiplication contributes by \(\binom{n}{0} \cdot \binom{n}{n}\) to the coefficient of \(x^n y^n\) in \((x+y)^{2n}\text{.}\) Similarly, take the term \(x^{n-1}y\) from the first factor, this must be multiplied by \(xy^{n-1}\) from the second factor to obtain \(x^n y^n\text{.}\) The coefficient of \(x^{n-1}y\) in the first factor is \(\binom{n}{1}\text{,}\) the coefficient of \(xy^{n-1}\) in the second factor is \(\binom{n}{n-1}\text{,}\) thus this multiplication contributes by \(\binom{n}{1} \cdot \binom{n}{n-1}\) to the coefficient of \(x^n y^n\) in \((x+y)^{2n}\text{.}\) In general, for some \(k\) the term \(x^{n-k}y^k\) in the first factor must be multiplied by \(x^k y^{n-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^ky^{n-k}\) in the second factor is \(\binom{n}{n-k}\text{,}\) thus this multiplication contributes by \(\binom{n}{k} \cdot \binom{n}{n-k}\) to the coefficient of \(x^n y^n\) in \((x+y)^{2n}\text{.}\) That is, the coefficient of \(x^n y^n\) in \((x+y)^{2n}\) is
\begin{equation*} \sum_{k=0}^n \binom{n}{k} \cdot \binom{n}{n-k}\text{.} \end{equation*}Moreover, the coefficient of \(x^ny^n\) in \((x+y)^{2n}\) is \(\binom{2n}{n}\text{,}\) thus the two numbers must be equal. Applying the symmetry of Pascal's triangle (that is, \(\binom{n}{k} = \binom{n}{n-k}\)), we obtain (4.2.2):
\begin{equation*} \sum_{k=0}^n \binom{n}{k}^2 = \sum_{k=0}^n \binom{n}{k} \cdot \binom{n}{n-k} = \binom{2n}{n}\text{.} \end{equation*}Exercise4.2.6
Solve Exercise 4.2.5 using the Binomial theorem.
After dealing with sums of rows, consider sums where we move diagonally upwards. That is, when we sum up the \(m\)th elements of every row. For \(m=0\) it is pretty easy:
\begin{equation*} \binom{n}{0} + \binom{n-1}{0} + \dots + \binom{1}{0} + \binom{0}{0} = n+1\text{.} \end{equation*}For \(m=1\) we have
\begin{equation*} \binom{n}{1} + \binom{n-1}{1} + \dots + \binom{2}{1} + \binom{1}{1} = n + (n-1) + \dots + 2 + 1 = \frac{n\cdot (n+1)}{2}\text{,} \end{equation*}For \(m=2\) it is a bit harder to do the calculations, but still manageable:
\begin{align*} \amp \binom{n}{2} + \binom{n-1}{2} + \dots + \binom{3}{2} + \binom{2}{2}\\ \amp = \frac{n \cdot (n-1)}{2} + \frac{(n-1) \cdot (n-2)}{2} + \dots + \frac{3 \cdot 2}{2} + \frac{2 \cdot 1}{2}\\ \amp = \frac12 \cdot \left( n \cdot (n-1) + (n-1) \cdot (n-2) + \dots + 3 \cdot 2 + 2 \cdot 1 \right)\\ \amp = \frac12 \cdot \frac{(n+1) \cdot n \cdot (n-1)}{3} = \frac{(n+1) \cdot n \cdot (n-1)}{3 \cdot 2 \cdot 1}\text{.} \end{align*}Here, we used Exercise 3.1.9 to calculate the sum \(\sum_{i=1}^{n-1} i \cdot (i+1)\text{.}\)
It is quite clear that by increasing \(m\text{,}\) we would have harder and harder time to calculate the obtained sums. Nevertheless, only by computing the first couple sums we can make a guess at the general answer:
\begin{align*} \amp \text{ for \(m=0\) } \amp \sum_{k=0}^n \binom{k}{0} \amp = n+1,\\ \amp \text{ for \(m=1\) } \amp \sum_{k=1}^n \binom{k}{1} \amp = \frac{(n+1) \cdot n}{2},\\ \amp \text{ for \(m=2\) } \amp \sum_{k=2}^n \binom{k}{2} \amp = \frac{(n+1) \cdot n \cdot (n-1)}{3 \cdot 2}\text{.} \end{align*}Now, hold on for a second! The right hand sides here are \(\binom{n+1}{1}\text{,}\) \(\binom{n+1}{2}\text{,}\) \(\binom{n+1}{3}\text{,}\) respectively. From this, we may conjecture that in general the sum \(\sum_{k=m}^n \binom{k}{m}\) will be \(\binom{n+1}{m+1}\text{.}\) This is indeed the case.
Proposition4.2.7
The sum of \(m\)th elements of Pascal's triangle is \(\binom{n+1}{m+1}\text{,}\) that is,
\begin{equation} \sum_{k=m}^n \binom{k}{m} = \binom{m}{m} + \binom{m+1}{m} + \dots + \binom{n}{m} = \binom{n+1}{m+1}\text{.}\label{eq_sumkchoosem}\tag{4.2.3} \end{equation}Proof
We prove the proposition by induction on \(n\text{.}\) Fix \(m\) first, then the induction starts by checking if the statement holds for the smallest possible \(n\text{,}\) that is, for \(n = m\text{.}\) For \(n=m\) the left hand side is simply \(\binom{m}{m} = 1\text{,}\) the right hand side is \(\binom{m+1}{m+1} = 1\text{,}\) and the statement holds. Let us assume now that the statement holds for \(n-1\text{,}\) that is,
\begin{equation*} \sum_{k=m}^{n-1} \binom{k}{m} = \binom{m}{m} + \binom{m+1}{m} + \dots + \binom{n-1}{m} = \binom{n}{m+1}\text{.} \end{equation*}This is the induction hypothesis. Now we prove that the statement holds for \(n\text{,}\) as well. Consider the sum \(\sum_{k=m}^{n} \binom{k}{m}\text{:}\)
\begin{align*} \amp \sum_{k=m}^{n} \binom{k}{m} = \underbrace{\binom{m}{m} + \binom{m+1}{m} + \dots + \binom{n-1}{m}}_{= \binom{n}{m+1}, \text{ by the induction hypothesis } } + \binom{n}{m}\\ \amp = \binom{n}{m+1} + \binom{n}{m} = \binom{n+1}{m+1}\text{.} \end{align*}Here, we first used the induction hypothesis, then the generating rule of Pascal's triangle (Proposition 4.0.3).
Again, the induction proof clearly settles that our conjecture was true, but it does not clarify the reason why this identity holds. By finding combinatorial meaning to both sides of (4.2.3), we can understand what is “behind the curtain”.
Proof
Again, the right hand side gives a clue on what we need to find. Since \(\binom{n+1}{m+1}\) is the number of ways choosing \(m+1\) elements out of an \(n\)-element set, this is what we will try to find on the left hand side, as well. Let \(S= \halmaz{1, 2, \dots , n, n+1}\text{.}\) Try to choose \(m+1\) elements in the following way: first choose the largest one, then choose the remaining \(m\) elements. Clearly the largest is at least \(m+1\text{.}\) If we choose \(m+1\) as the largest chosen number, then we need to choose \(m\) elements out of the \(m\)-element set \(\halmaz{1, 2, \dots , m}\text{,}\) this can be done in \(\binom{m}{m}\)-many ways. If we choose \(m+2\) as the largest chosen number, then we need to choose \(m\) elements out of the \((m+1)\)-element set \(\halmaz{1, 2, \dots , m+1}\text{,}\) this can be done in \(\binom{m+1}{m}\)-many ways. If we choose \(m+3\) as the largest chosen number, then we need to choose \(m\) elements out of the \((m+2)\)-element set \(\halmaz{1, 2, \dots , m+2}\text{,}\) this can be done in \(\binom{m+2}{m}\)-many ways. In general, if we choose \(k+1\) as the largest chosen number (for some \(m \leq k\leq n\)), then we need to choose \(m\) elements out of the \(k\)-element set \(\halmaz{1, 2, \dots , k}\text{,}\) this can be done in \(\binom{k}{m}\)-many ways. If we choose \(n\) as the largest chosen number, then we need to choose \(m\) elements out of the \((n-1)\)-element set \(\halmaz{1, 2, \dots , n-1}\text{,}\) this can be done in \(\binom{n-1}{m}\)-many ways. Finally, if we choose \(n+1\) as the largest chosen number, then we need to choose \(m\) elements out of the \(n\)-element set \(\halmaz{1, 2, \dots , n}\text{,}\) this can be done in \(\binom{n}{m}\)-many ways. That is, the number of ways we can choose \((m+1)\) elements out of an \((n+1)\)-element set is
\begin{equation*} \sum_{k=m}^n \binom{k}{m} = \binom{m}{m} + \binom{m+1}{m} + \dots + \binom{n}{m} \end{equation*}on the one hand, and \(\binom{n+1}{m+1}\) on the other hand. Thus the two numbers must be equal, as they count the same thing. Hence,
\begin{equation*} \sum_{k=m}^n \binom{k}{m} = \binom{m}{m} + \binom{m+1}{m} + \dots + \binom{n}{m} = \binom{n+1}{m+1}\text{.} \end{equation*}Note, that from this identity we immediately obtain a formula for the sum of integer numbers and for the sum of squares. Indeed,
\begin{equation*} 1 + 2 + \dots + n = \sum_{k=1}^n {k} = \sum_{k=1}^n \binom{k}{1} = \binom{n+1}{2} = \frac{(n+1) \cdot n}{2}\text{,} \end{equation*}because \(k\) in \(\sum_{k=1}^n k\) can be expressed as \(\binom{k}{1}\text{.}\) Similarly, \(k^2 = \binom{k+1}{2} + \binom{k}{2}\) by Exercise 2.6.11 (for \(k\geq 2\)). Thus
\begin{align*} 1^2 + 2^2 + \dots + n^2 \amp = \sum_{k=1}^n k^2 = 1 + \sum_{k=2}^n \left(\binom{k+1}{2} + \binom{k}{2}\right)\\ \amp = 1 + \sum_{k=2}^n \binom{k+1}{2} + \sum_{k=2}^n \binom{k}{2}\\ \amp = \binom{2}{2} + \sum_{k=2}^n \binom{k+1}{2} + \sum_{k=2}^n \binom{k}{2}\\ \amp = \sum_{k=1}^{n} \binom{k+1}{2} + \sum_{k=2}^n \binom{k}{2} = \sum_{k=2}^{n+1} \binom{k}{2} + \sum_{k=2}^n \binom{k}{2}\\ \amp = \binom{n+2}{3} + \binom{n+1}{3}\\ \amp = \frac{(n+2) \cdot (n+1) \cdot n}{3 \cdot 2} + \frac{(n+1) \cdot n \cdot (n-1)}{3 \cdot 2}\\ \amp = \frac{n \cdot (n+1)}{3 \cdot 2} \cdot \left( (n+2)+ (n-1) \right)\\ \amp = \frac{n \cdot (n+1) \cdot (2n+1)}{6}\text{.} \end{align*}Exercise4.2.8
Prove a similar identity for summing up numbers diagonally in the other direction:
\begin{equation} \sum_{k=0}^m \binom{n+k}{k} = \binom{n}{0} + \binom{n+1}{1} + \dots + \binom{n+m}{m} = \binom{n+m+1}{m}\text{.}\tag{4.2.4} \end{equation}Exercise4.2.9
Let \(p\) be a prime. Prove that every number in row \(p\) (except for the first and last) is divisible by \(p\text{.}\) By observing the first 12 rows of Pascal's triangle, confirm that this property does not necessarily hold if \(p\) is not a prime.