This is Pascal's Triangle. Each number, other than the 1 in the top row, is the sum of the 2 numbers above it (imagine that there are 0s surrounding the triangle). We often number the rows starting with row 0. We also often number the numbers in each row going from left to right, with the leftmost number being the 0th number in that row. For example, the 1st number in row 2 would be 2 (the 1 to the left of the 2 is the 0th number in the row). Try to look for some of the many patterns in Pascal's Triangle. In this lesson, we will prove some of these patterns.
Sample Problem 1. Prove that the kth number in the nth row is \(\binom{n}{k}\).
We will prove this by explaining another interpretation of the number in each place. We will interpret each number as the number of ways to get to the position of the number by only moving down and left one or down and right one. We can confirm that this interpretation works because the number of ways to get to any position is equal to the sum of the number of ways to get to either of the positions directly above it (as these two positions are the only ones that could lead to the one below both of them). However, we can note that to get to the position of the kth number in the nth row, we have to go down n times -- and of those times, exactly k must be down and to the right, while the others are down and to the left (if you can't see this immediately, imagine going down and to the left n times to end up on the 0th number in the nth row). Thus, the number of ways to get to the kth number in the nth row is \(\binom{n}{k}\) because that is how many ways we can choose which k of the n moves down are also to the right.
The idea of looking at each number represent these two different things is a very useful one. Using this technique, we can prove many useful identities about binomial coefficients.
The idea of looking at each number represent these two different things is a very useful one. Using this technique, we can prove many useful identities about binomial coefficients.
Sample Problem 2. Find the coefficient of the \(x^k\) in \((x+y)^n\).
It isn't immediately apparent what the coefficients could be or how to find them, so we will start by looking at some examples. \[(x+y)^0=1\] \[(x+y)^1=x+y\] \[(x+y)^2 =x^2+2xy+y^2\] \[(x+y)^3=x^3+3x^2y+3xy^2+y^3\] \[(x+y)^4=x^4+4x^3y+6x^2y^2+4xy^3+y^4\] Does this look familiar? It appears that the coefficients \((x+y)^n\) are exactly the numbers in the nth row of Pascal's Triangle.
We now want to figure out how to prove this. As we just saw in the last problem, we can rewrite the numbers in Pascal's Triangle as binomial coefficients. We will thus rewrite the coefficients of our expanded polynomials to see if we notice anything. \[(x+y)^0=\binom{0}{0}\] \[(x+y)^1=\binom{1}{0}x+\binom{1}{1}y\] \[(x+y)^2 =\binom{2}{0}x^2+\binom{2}{1}xy+\binom{2}{2}y^2\] \[(x+y)^3=\binom{3}{0}x^3+\binom{3}{1}x^2y+\binom{3}{2}xy^2+\binom{3}{3}y^3\]\[(x+y)^4=\binom{4}{0}x^4+\binom{4}{1}x^3y+\binom{4}{2}x^2y^2+\binom{4}{3}xy^3+\binom{4}{4}y^4\] To start, we will note that the coefficient of the \(x^k\) term is the same as the coefficient of the \(y^k\) term. It would also appear that the coefficient of the \(y^k\) term in \((x+y)^n\) is \(\binom{n}{k}.\) Thus, we conjecture that the coefficient of the \(x^k\) term in \((x+y)^n\) is \(\binom{n}{k}.\)
There is a fairly intuitive explanation for why this is true. When we expand \((x+y)^n\) we are essentially adding together all the combinations of choosing an x or a y from each of n terms being multiplied together. Thus, we are essentially just adding together each of the \(\binom{n}{k}\) ways to choose which k of the n terms contribute an x. This also provides a nice explanation for why the \(x^k\) and \(y^k\) terms have the same coefficient: using what we just discovered, the coefficients are \(\binom{n}{k}\) and \(\binom{n}{n-k}\) respectively (the power of the x and y term must clearly always add up to n using the explanation we gave earlier of how to expanding \((x+y)^n\)) and \(\binom{n}{k}\)=\(\binom{n}{n-k}\) (if this last statement isn't clear think about how choosing k things to include is equivalent to choosing n-k things not to include). This statement about the coefficients of a binomial raised to a positive integral power is called the Binomial Theorem.
We now want to figure out how to prove this. As we just saw in the last problem, we can rewrite the numbers in Pascal's Triangle as binomial coefficients. We will thus rewrite the coefficients of our expanded polynomials to see if we notice anything. \[(x+y)^0=\binom{0}{0}\] \[(x+y)^1=\binom{1}{0}x+\binom{1}{1}y\] \[(x+y)^2 =\binom{2}{0}x^2+\binom{2}{1}xy+\binom{2}{2}y^2\] \[(x+y)^3=\binom{3}{0}x^3+\binom{3}{1}x^2y+\binom{3}{2}xy^2+\binom{3}{3}y^3\]\[(x+y)^4=\binom{4}{0}x^4+\binom{4}{1}x^3y+\binom{4}{2}x^2y^2+\binom{4}{3}xy^3+\binom{4}{4}y^4\] To start, we will note that the coefficient of the \(x^k\) term is the same as the coefficient of the \(y^k\) term. It would also appear that the coefficient of the \(y^k\) term in \((x+y)^n\) is \(\binom{n}{k}.\) Thus, we conjecture that the coefficient of the \(x^k\) term in \((x+y)^n\) is \(\binom{n}{k}.\)
There is a fairly intuitive explanation for why this is true. When we expand \((x+y)^n\) we are essentially adding together all the combinations of choosing an x or a y from each of n terms being multiplied together. Thus, we are essentially just adding together each of the \(\binom{n}{k}\) ways to choose which k of the n terms contribute an x. This also provides a nice explanation for why the \(x^k\) and \(y^k\) terms have the same coefficient: using what we just discovered, the coefficients are \(\binom{n}{k}\) and \(\binom{n}{n-k}\) respectively (the power of the x and y term must clearly always add up to n using the explanation we gave earlier of how to expanding \((x+y)^n\)) and \(\binom{n}{k}\)=\(\binom{n}{n-k}\) (if this last statement isn't clear think about how choosing k things to include is equivalent to choosing n-k things not to include). This statement about the coefficients of a binomial raised to a positive integral power is called the Binomial Theorem.
Note: The Binomial Theorem does in fact work for a binomial raised to any power, but the proof is much too complicated to cover in this curriculum, and it far beyond this level of math. This extended binomial theorem also uses a definition of binomial coefficients that is adapted to be used with non-integers and negatives. If you want to find out more, a quick google search for Extended Binomial Theorem or Generalized Binomial Theorem should do. This theorem can also be generalized beyond binomials, where it is called the Multinomial Theorem. A quick google search for Multinomial Thoerem should give information about that.
Exercises
- Prove that the sum of the numbers in the nth row of Pascal's Triangle is \(2^n\).
- Prove that \( \binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}\).
- Prove that \(\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+\ldots +\binom{n+d}{n}=\binom{n+d+1}{n+1}\).
Solution 1
By the Binomial Theorem, when we expand \((1+1)^n=2^n\) we merely get the sum of the numbers in the nth row of pascals triangle.
Solution 2
There are several ways to prove this identity, we will just show one. Using pascals triangle, we know that each number is equal to the sum of the two numbers directly above it. In other words, we get that the sum of the kth and k+1th numbers in the nth row is equal to the kth number in the n+1th row. However, using the binomial coefficient definition of Pascal's triangle, we get can restate the above to get \( \binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}\), which is exactly what we wanted.
This identity that we just proved is called Pascal's Identity.
This identity that we just proved is called Pascal's Identity.
Solution 3
There are again several ways to prove this. We will only show an algebraic proof here, but we encourage you to try to find another proof using Pascal's Triangle as we did in the above solution.
We will preform the following steps using Pascal's Identity (exercise 2) and basic properties of binomial coefficients:
\[\begin{align*}
&\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+\ldots +\binom{n+d}{n} \\
&=\binom{n+1}{n+1}+\binom{n+1}{n}+\binom{n+2}{n}+\ldots +\binom{n+d}{n}\\
&=\binom{n+2}{n+1}+\binom{n+2}{n}+\ldots +\binom{n+d}{n}\\
&=\binom{n+3}{n+1}+\ldots +\binom{n+d}{n}\\
&\ldots\\
&=\binom{n+d}{n+1}+\binom{n+d}{n}\\
&=\binom{n+d+1}{n+1}.\\
\end{align*}\]
And thus, we are done.
We will preform the following steps using Pascal's Identity (exercise 2) and basic properties of binomial coefficients:
\[\begin{align*}
&\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+\ldots +\binom{n+d}{n} \\
&=\binom{n+1}{n+1}+\binom{n+1}{n}+\binom{n+2}{n}+\ldots +\binom{n+d}{n}\\
&=\binom{n+2}{n+1}+\binom{n+2}{n}+\ldots +\binom{n+d}{n}\\
&=\binom{n+3}{n+1}+\ldots +\binom{n+d}{n}\\
&\ldots\\
&=\binom{n+d}{n+1}+\binom{n+d}{n}\\
&=\binom{n+d+1}{n+1}.\\
\end{align*}\]
And thus, we are done.