Editing Pascal's triangle (section)

== Binomial expansions ==
[[File:Binomial theorem visualisation.svg|thumb|upright=1.25|Visualisation of binomial expansion up to the 4th power]]

Pascal's triangle determines the coefficients which arise in [[binomial expansion]]s. For example, in the expansion
<math display="block">(x + y)^2 = x^2 + 2xy + y^2 = \mathbf{1} x^2 y^0 + \mathbf{2} x^1 y^1 + \mathbf{1} x^0 y^2,</math>
the coefficients are the entries in the second row of Pascal's triangle: <math>\tbinom 20 = 1</math>, <math>\tbinom 21 = 2</math>, <math>\tbinom 22 = 1</math>.

In general, the [[binomial theorem]] states that when a [[binomial (polynomial)|binomial]] like <math>x + y</math> is raised to a positive integer power <math>n</math>, the expression expands as
<math display="block">(x + y)^n = 
\sum_{k=0}^{n} a_{k} x^{n-k} y^{k} = 
a_{0} x^n + a_{1} x^{n - 1} y + a_{2} x^{n - 2} y^{2} + \ldots + a_{n - 1} x y^{n-1} + a_{n} y^{n}, </math>
where the coefficients <math>a_{k} </math> are precisely the numbers in row <math>n </math> of Pascal's triangle:
<math display="block">a_k = {n \choose k}.</math>

The entire left diagonal of Pascal's triangle corresponds to the coefficient of <math>x^n </math> in these binomial expansions, while the next left diagonal corresponds to the coefficient of <math>x^{n-1} y </math>, and so on.

To see how the binomial theorem relates to the simple construction of Pascal's triangle, consider the problem of calculating the coefficients of the expansion of <math>(x + y)^{n + 1} </math> in terms of the corresponding coefficients of <math>(x + 1)^{n} </math>, where we set <math>y = 1 </math> for simplicity. Suppose then that
<math display="block">
(x + 1)^{n} = \sum_{k = 0}^{n} a_{k} x^{k}.
</math>
Now
<math display="block"> (x+1)^{n+1} = (x+1)(x+1)^n = x(x+1)^n + (x+1)^n = \sum_{i=0}^n a_i x^{i+1} + \sum_{k=0}^n a_k x^k.</math>

{{Image frame|width=260|caption=The first six rows of Pascal's triangle as binomial coefficients
|content=
<math>\begin{array}{c}
\dbinom{0}{0} \\
                                \dbinom{1}{0} \quad \dbinom{1}{1} \\
                        \dbinom{2}{0} \quad \dbinom{2}{1} \quad \dbinom{2}{2} \\
                \dbinom{3}{0} \quad \dbinom{3}{1} \quad \dbinom{3}{2} \quad \dbinom{3}{3} \\
        \dbinom{4}{0} \quad \dbinom{4}{1} \quad \dbinom{4}{2} \quad \dbinom{4}{3} \quad \dbinom{4}{4} \\
\dbinom{5}{0} \quad \dbinom{5}{1} \quad \dbinom{5}{2} \quad \dbinom{5}{3} \quad \dbinom{5}{4} \quad \dbinom{5}{5}
\end{array}</math>
}}

The two summations can be reindexed with <math>k=i+1 </math> and combined to yield
<math display="block">
\begin{align}
\sum_{i=0}^{n} a_{i} x^{i+1} + \sum_{k=0}^n a_k x^k &= 
\sum_{k=1}^{n+1} a_{k-1} x^{k} + \sum_{k=0}^n a_k x^k \\ [4pt] &= 
\sum_{k=1}^{n} a_{k-1} x^{k}  + a_{n}x^{n+1} + a_0x^0 + \sum_{k=1}^n a_k x^k \\[4pt] &= 
a_0x^0 + \sum_{k=1}^{n} (a_{k-1} + a_k)x^{k} + a_{n}x^{n+1} \\[4pt] &= 
x^0 + \sum_{k=1}^{n} (a_{k-1} + a_k)x^{k} + x^{n+1}.
\end{align}
</math>

Thus the extreme left and right coefficients remain as 1, and for any given <math>0 < k < n + 1 </math>, the coefficient of the <math>x^{k} </math> term in the polynomial <math>(x + 1)^{n + 1} </math> is equal to <math>a_{k-1} + a_{k} </math>, the sum of the <math>x^{k-1} </math> and <math>x^{k} </math> coefficients in the previous power <math>(x + 1)^n </math>. This is indeed the downward-addition rule for constructing Pascal's triangle.

It is not difficult to turn this argument into a [[proof (mathematics)|proof]] (by [[mathematical induction]]) of the binomial theorem.

Since <math>(a + b)^{n} = b^{n}(\tfrac{a}{b} + 1 )^{n} </math>, the coefficients are identical in the expansion of the general case.

An interesting consequence of the binomial theorem is obtained by setting both variables <math>x = y = 1 </math>, so that
<math display="block"> \sum_{k = 0}^{n} {n \choose k} 
= {n \choose 0} + {n \choose 1} + \cdots + {n \choose n-1} + {n \choose n}
= (1+1)^n = 2^{n}. </math>

In other words, the sum of the entries in the <math>n</math>th row of Pascal's triangle is the <math>n</math>th power of&nbsp;2. This is equivalent to the statement that the number of subsets of an <math>n</math>-element set is <math>2^n</math>, as can be seen by observing that each of the <math>n</math> elements may be independently included or excluded from a given subset.