Pascal's triangle: Difference between revisions

Revision as of 14:20, 23 May 2007

Revision as of 14:46, 23 May 2007

Line 51:

1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1

==Uses of Pascal's triangle and binomial expansions==

Pascal's triangle hasdetermines manythe usescoefficients which arise in [[binomial expansionsexpansion]]s. For a example:, consider the expansion

:(''x'' + ''y'')² = ''x''² + 2''xy'' + ''y''² = '''1'''''x''²''y''⁰ + '''2'''''x''¹''y''¹ + '''1'''''x''⁰''y''².

Notice the coefficients are the thirdnumbers in row two of Pascal's triangle: 1, 2, 1.

In general, when a [[binomial]] like ''x'' + ''y'' is raised to a positive integer power we have:

:(''x'' + ''y'')^''n'' = ''a''₀''x''^''n'' + ''a''₁''x''^{''n''−1}''y'' + ''a''₂''x''^{''n''−2}''y''² + … + ''a''_{''n''−1}''xy''^{''n''−1} + ''a''_''n''''y''^''n'',

where the coefficients ''a''_''i'' in this expansion are precisely the numbers on row ''n'' + 1 of Pascal's triangle. Thus:In other words,

:<math>a_i = {n \choose i}.</math>

Line 68:

This is the [[binomial theorem]].

In order to prove this theorem, one must start by consideringNotice that the entire right diagonal of Pascal's triangle corresponds to the coefficient of ''xy''^0''n'' whenin (''x''&nbsp;+&nbsp;1)these hasbinomial beenexpansions, raised to some power equal towhile the row number. The next diagonal corresponds to the coefficient of ''xxy''¹, and so on. Now, algebraically, we are trying to determine what (''x''&nbsp;+&nbsp;1)^''n''+-1 looksand like,so if we start by defining (''x''&nbsp;+&nbsp;1)^''n'' as being equal toon.

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 (''x''&nbsp;+&nbsp;1)^''n''+1 in terms of the corresponding coefficients of (''x''&nbsp;+&nbsp;1)^''n'' (setting ''y'' = 1 for simplicity). Suppose then that

:<math>\sum_{i=0}^n a_i x^i</math>

:<math>(x+1)^n=\sum_{i=0}^n a_i x^i.</math>

Now

Line 76 ⟶ 78:

:<math>(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_{i=0}^n a_i x^i</math>

The two summations can be reorganized as follows:

Next we clean up the summations:

::<math>\sum_{i=0}^{n } a_{i } x^{i+1} + \sum_{i=0}^n a_i x^i = </math>

Line 84 ⟶ 86:

::<math>\sum_{i=1}^{n } (a_{i-1} + a_i)x^{i } + x^0 + x^{n+1}</math> (because of how raising a polynomial to a power works, ''a''₀ = ''a''_''n'' = 1)

We now have an expression for the polynomial (''x''&nbsp;+&nbsp;1)^''n''+1 in terms of the coefficients of (''x''&nbsp;+&nbsp;1)^''n'' (these are the ''a''_''i''s), which is what we need if we want to express a line in terms of the line above it. Recall that all the terms in a diagonal going from the upper-left to the lower-right correspond to the same power of ''x'', and that the a-terms are the coefficients of the polynomial (''x''&nbsp;+&nbsp;1)^''n'', and we are determining the coefficients of (''x''&nbsp;+&nbsp;1)^''n''+1. Now, for any given ''i'' not 0 or ''n''&nbsp;+&nbsp;1, the coefficient of the ''x''^''i'' term in the polynomial (''x''&nbsp;+&nbsp;1)^''n''+1 is equal to ''a''_''i'' (the figure above and to the left of the figure to be determined, since it is on the same diagonal) + ''a''_{''i''&minus;1} (the figure to the immediate right of the first figure). Inspecting Pascal's triangle, we find that thisThis is indeed the simple rule atfor theconstructing beginningPascal's of thetriangle articlerow-by-row.

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

One veryAn interesting consequence of thisthe factbinomial theorem is obtained by substitutingsetting theboth numbervariables one''x'' forand ''xy'' equal to one. In this case, we know that <math> (1+1)^n = 2^n </math>, hence the sumand ofso

:<math> {n \choose 0} + {n \choose 1} + \cdots +{n \choose n-1} + {n \choose n} = 2^n. </math>

ThatIn is toother saywords, the sum of the entries in the ''in''th row of Pascal's triangle sum tois the ''in''th power of 2.

==Properties of Pascal's triangle==