Pascal's triangle: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Olier Raby
(→‎Properties: Shortened.)
mNo edit summary
 
(120 intermediate revisions by 12 users not shown)
Line 1: Line 1:
The '''Pascal's triangle''' is a convenient tabular presentation for the [[binomial coefficients]]. Already known in the 11th century<ref>[http://www-gap.dcs.st-and.ac.uk/~history/Biographies/Al-Karaji.html ''Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji''], School of Mathematics and Statistics, University of St Andrews. Consulted 2005-09-03.</ref>, it was adopted in [[Western world]] under this name after [[Blaise Pascal]] published his ''Traité du triangle arithmétique'' ("Treatise on the Arithmetical Triangle") in 1654.
{{subpages}}
'''Pascal's triangle''' is a convenient tabular representation of the [[binomial coefficient]]s. Already known in the 11th century,<ref>[http://www-gap.dcs.st-and.ac.uk/~history/Biographies/Al-Karaji.html ''Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji''], School of Mathematics and Statistics, University of St Andrews. Consulted 2005-09-03.</ref> it was adopted in the [[Western world]] under this name after [[Blaise Pascal]] published his ''Traité du triangle arithmétique'' ("Treatise on the Arithmetical Triangle") in 1654.


For instance, we can use Pascal's triangle to compute the binomial expansion of
Pascal's triangle appears under different formats. Here is its most common:


:<math>(x+y)^4 = 1 \times a^4 + 4 \times a^3b + 6 \times a^2b^2 + 4 \times ab^3  + 1 \times b^4 ~</math>
The [[coefficient]]s 1, 4, 6, 4, 1 appear directly in the triangle.
<center>
<center>
<math>
<math>
\begin{matrix}
    \begin{array}{cccccccccccc}
&&&&&1\\
&  &   &   &   &   & 1 &  &  &  &  &    \\
&&&&1&&1\\
&   &   &   &   &  1&   & 1 &  &  &  &    \\
&&&1&&2&&1\\
&  &   &   & 1 &   & 2 &   & 1 &  &  &    \\
&&1&&3&&3&&1\\
&   &  & 1 &   & 3&   & 3&   & 1 &  &    \\
&1&&4&&6&&4&&1\\
&  & 1 &   & 4 &   & 6 &   & 4 &   & 1 &    \\
&&&&&\cdots
& 1 &  & 5 &  & 10&  & 10&  & 5 &  & 1 \\
\end{matrix}
&   &   &   &   &  &\cdots&&  &  &  &
\end{array}
</math>
</math>
</center>
</center>


We can use Pascal's triangle to compute the [[binomial expansion]] of <math>\scriptstyle (x + y)^n</math>. For instance,
:<math> (x+y)^4 = 1 \times x^4 + 4 \times x^3y + 6 \times x^2y^2 + 4 \times xy^3  + 1 \times y^4 </math>
The triangle shows the [[coefficient]]s <math>\scriptstyle 1, 4, 6, 4, 1</math> on the fifth row.
Pascal's triangle has applications in [[algebra]] and in [[Probability theory|probabilities]]. We can use it to compute the [[Fibonacci number]]s and to create the [[Sierpinski triangle]]. After studying it, [[Isaac Newton]] expanded the triangle and found new methods to extract the [[square root]] and to calculate the natural [[logarithm]] of a number.
== History ==
{{Image|Pascal's triangle - Yanghui triangle.PNG|right|200px|Drawing of Pascal's Triangle published in 1303 by Zhu Shijie (1260-1320), in his Si Yuan Yu Jian. It was called Yanghui Triangle by the Chinese, after the mathematician Yang Hui.<br>The fourth entry from the left in the second row from the bottom appears to be a typo (34 instead of 35, correctly given in the fifth entry in the same row).}}
The earliest explicit depictions of a triangle of [[binomial coefficients]] occur in the 10th century in commentaries on the ''Chandas Shastra'', an ancient Indian book on [[Sanskrit]] [[prosody]] written by [[Pingala]] between the 5th century BC and 2nd century BC. While Pingala's work only survives in fragments, the commentator [[Halayudha]], around 975, used the triangle to explain obscure references to ''Meru-prastaara'', the "Staircase of Mount Meru". It was also realised that the shallow diagonals of the triangle sum to the [[Fibonacci number]]s. The Indian mathematician Bhattotpala (c. 1068) later gives rows 0-16 of the triangle.
At around the same time, it was discussed in [[Persia]] by the mathematician [[Al-Karaji]] (953–1029) and the poet-astronomer-mathematician [[Omar Khayyám]] (1048-1131); thus the triangle is referred to as the "Khayyam triangle" in Iran. Several theorems related to the triangle were known, including the [[binomial theorem]]. It seems that Khayyam used a method of finding ''n''th roots based on the binomial expansion, and therefore on the binomial coefficients.
In 13th century, [[Yang Hui]] (1238-1298) presented an arithmetic triangle, which was the same as Pascal's Triangle. Today, Pascal's triangle is called "Yang Hui's triangle" in China. In [[Italy]], it is known as "Tartaglia's triangle", named for the Italian algebraist [[Niccolo Fontana Tartaglia]] who lived a century before Pascal.
In 1655, [[Blaise Pascal]] published its ''Traité du triangle arithmétique'' ("Treatise on arithmetical triangle"), wherein he collected several results then known about the triangle, and employed them to solve problems in [[Probability theory|probabilities]]. The triangle was later named after Pascal by [[Pierre Raymond de Montmort]] (1708) and [[Abraham de Moivre]] (1730).
After that, even if it was useful in many areas of mathematics, most research was done within its descendants, like probabilities and [[combinatorics]].
== Some Properties ==
Each term in the triangle is the sum of the two terms above it<ref name="not_for_ones">This rule does not apply to the ones bordering the triangle. We just insert them.</ref>. For instance, <math>\scriptstyle 6 = 3 + 3</math>. The binomial coefficients relate to this construction by Pascal's rule, which states that if


Each coefficient in the triangle is the sum of the two coefficients over it<ref name="not_for_ones">This rule does not apply to the ones bordering the triangle. We just insert them.</ref>. For instance, <math>6 = 3 + 3</math>. The binomial coefficients relate to this construction by Pascal's rule, which states that if
:<math> {n \choose k} = \frac{n!}{k! (n-k)!} </math>
:<math> {n \choose k} = \frac{n!}{k! (n-k)!} </math>
is the ''k''th binomial coefficient in the [[binomial expansion]] of (''x''+''y'')<sup>''n''</sup>, then


:<math> {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}</math>
is the ''k''th binomial coefficient in the [[binomial expansion]] of <math>\scriptstyle (x + y)^n</math>, then


for any nonnegative integer ''n'' and any integer ''k'' between 0 and ''n''.<ref>By convention, the binomial coefficient <math>\scriptstyle {n \choose k}</math> is set to zero if ''k'' is either less than zero or greater than ''n''.</ref>
:<math> {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} \text{ with } k, n \in \N^* \text{ and } 0 \leq k \leq n </math>


Those coefficients have applications in [[algebra]] and in [[probabilities]]. From the triangle, we can equally compute the [[Fibonacci number]]s and create the [[Sierpinski triangle]]. After studying it, [[Isaac Newton]] expanded it and found new methods to extract the [[square root]] and to calculate the natural [[logarithm]] of a number.
By convention, the binomial coefficient <math>\scriptstyle {n \choose k}</math> is set to zero if <math>\scriptstyle k</math> is either less than zero or greater than <math>\scriptstyle n</math>.


== Properties ==
To better understand some properties, the triangle is presented differently :
In order to ease the understanding of some properties, the triangle should be presented differently :




Line 51: Line 68:
</div>
</div>


 
Each coefficient is the sum of the coefficient exactly over it and its left neighbour<ref name="not_for_ones"/>. For instance, <math>\scriptstyle 3 + 3 = 6</math>. Let's call this rule the "addition rule".
Each coefficient is the sum of the coefficient exactly over it and the other to its left. For instance, <math>3 + 3 = 6</math>.  
 
Let's call this rule the "addition rule"<ref name="not_for_ones"/>.


Using this format, it is easy to apply an index to each row :  
Using this format, it is easy to apply an index to each row :  


<math>
<math>
Line 72: Line 85:
     \end{array}
     \end{array}
</math>
</math>


Starting the indices at zero facilitates many calculations.
Starting the indices at zero facilitates many calculations.


The sum of any row is <math>2^r~</math>, with <math>r~</math> being the row index : <math>0, 1, 2, \ldots ~</math> For instance, the sum of row 4 is <math> 1 + 4 + 6 + 4 + 1 = 16 = 2^4 ~</math>.
The sum of any row is <math>\scriptstyle 2^r</math>, with <math>\scriptstyle r</math> being the row index : <math>\scriptstyle 0, 1, 2, \ldots</math> For instance, the sum of row 4 is <math>\scriptstyle 1 + 4 + 6 + 4 + 1 = 16 = 2^4</math>.
 
Since there is a formula for summing a row, then maybe there is one for a column ? It is the case. Again, we index the triangle, but this time it will be the columns :


Since there is a formula for summing a row, then maybe there is one for a column ? It is the case. This time, we index the columns :


<math>
<math>
Line 96: Line 107:
</math>
</math>


Anyone familiar with the [[factorial]] function can easily find the general formula. The sum of a column <math>c~</math> ending at row <math>r~</math> is  
Anyone familiar with the [[factorial]] function can easily find the general formula. The sum of a column <math>\scriptstyle c</math> ending at row <math>\scriptstyle r</math> is  


:<math>\frac{(r+1)  \times r \, \times \cdots \times (r-c+1)}{(c + 1)!} \text{ with } r, c \in \N^*</math>.
:<math>\frac{(r+1)  \times r \, \times \cdots \times (r-c+1)}{(c + 1)!} \text{ with } r, c \in \N^*</math>.


There is another method to compute this sum, see <ref>Suppose we wish to add the terms in row 3, i.e. the fourth column, until row 6. The sum is given by multiplying four terms at [[numerator]], starting at <math>(r + 1) = 6 + 1 = 7~</math>, and four terms at the [[denominator]] starting at <math>(c + 1) = (3 + 1) = 4~</math>. The sum is equal to <math>\frac{ 7 \times 6 \times 5 \times 4 }{ 4 \times 3 \times 2 \times 1 } = 35~</math>. In short, fourth column, four terms at numerator, four terms at denominator, all decreasing.</ref>.
There is another method to compute this sum, see <ref>Suppose we wish to add the terms in row 3, i.e. the fourth column, until row 6. The sum is given by multiplying four terms at [[numerator]], starting at <math>\scriptstyle (r + 1) = 6 + 1 = 7</math>, and four terms at the [[denominator]] starting at <math>\scriptstyle (c + 1) = (3 + 1) = 4</math>. It is equal to <math>\scriptstyle \frac{ 7 \times 6 \times 5 \times 4 }{ 4 \times 3 \times 2 \times 1 } = 35</math>. In short, fourth column, four terms at numerator, four terms at denominator, all decreasing.</ref>.
 
Up until now, we added along the rows and the columns. We can add along the diagonals. Doing so from left to right and from bottom to top gives :
 
<math>
    \begin{array}{ccccccccccr}
        1 &  &  &  &  &  &  & = & 1  \\
        1 &  &  &  &  &  &  & = & 1  \\
        1 & + & 1 &  &  &  &  & = & 2  \\
        1 & + & 2 &  &  &  &  & = & 3  \\
        1 & + & 3 & + & 1 &  &  & = & 5  \\
        1 & + & 4 & + & 3 &  &  & = & 8  \\
        1 & + & 5 & + & 6 & + & 1 & = & 13 \\
        1 & + & 6 & + &10 & + & 4 & = & 21 \\
      ...&  &  &  &  &  &  & = &... \\
    \end{array}
</math>
 
The numbers on the right are the [[Fibonacci number]]s.
 
== One Row at a Time ==
We can build any row if we know the row before just by adding its terms two at a time. However, it is possible to build a row directly. We will build the row 4 in order to discover the rule. Each row starts with 1 :
 
<math>
    \begin{array}{lcccccc}
      4: & 1 & 4 & 6 & 4 & 1 & \\
    \end{array}
</math>
 
 
:<math> \scriptstyle 1 \times \frac{4 - 0}{1 + 0} = 4 ~</math>
 
:<math> \scriptstyle 4 \times \frac{4 - 1}{1 + 1} = 6 ~</math>
 
:<math> \scriptstyle 6 \times \frac{4 - 2}{1 + 2} = 4 ~</math>
 
:<math> \scriptstyle 4 \times \frac{4 - 3}{1 + 3} = 1 ~</math>
 
:<math> \scriptstyle 1 \times \frac{4 - 4}{1 + 4} = 0 ~</math>
 
:<math> \scriptstyle \cdots ~</math>
 
 
:<math> \binom{r}{c + 1}  = \binom{r}{c} \times \frac{r - c}{1 + c} \text{ with } r, c \in \N^* \text{ and } r \ge c ~</math><ref>Equally, we can compute any triangle's term using <math> \binom{r}{c} = \frac{ r! }{ c! (r - c)! }  \text{ with } r, c \in \N^* \text{ and } r \geq c ~</math>, but it may exceed the calculator capacity !</ref>
 
Once the row and the column indices are know, we can compute the neighbours, either right or left, of any term. Because it only applies to a row, we call it the "row rule".
 
== Polynomials with coefficients in triangle ==
* [[Binomial theorem]]
* [[Fibonacci polynomials]]
 
== Newton's Binomial Coefficients ==
[[Isaac Newton]] studied the triangle's properties and discovered two remarkable generalizations.<ref>Eli Maor, ''e: The Story of a Number'', Princeton University Press, 1994, p.71. ISBN 0-691-05854-7.</ref>
 
He extended the triangle along the negative axis. To better understand how he achieved this, let us write the triangle using another format :
 
<math>
    \begin{array}{lccccccccc}
        0: & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ... \\
        1: & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & ... \\
        2: & 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & ... \\
        3: & 1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & ... \\
        4: & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 & ... \\
        5: & 1 & 5 & 10& 10& 5 & 1 & 0 & 0 & ... \\
        6: & 1 & 6 & 15& 20& 15& 6 & 1 & 0 & ... \\
        7: & 1 & 7 & 21& 35& 35& 21& 7 & 1 & ... \\
        ...&...&...&...&...&...&...&...&...& ... \\
    \end{array}
</math>
 
[[Jacob Bernoulli]] is the "father" of this mathematical object named the "figurate number triangle"<ref>Eric W. Weisstein, ''CRC Concise Encyclopedia of Mathematics'', CRC Press, 1999, p. 636. ISBN 0-8493-9640-9</ref>. To ease the understanding in the following text, we will call it the "Bernoulli triangle", even if this [[matrix]] does not resemble a triangle anymore !
 
Using the row rule, let's compute the row -1 :
 
<math>
    \begin{array}{rrrrrrrr}
      -1: & 1 & -1& 1 & -1& 1 &-1 &... \\
        0: & 1 & 0 & 0 & 0 & 0 & 0 &... \\
        1: & 1 & 1 & 0 & 0 & 0 & 0 &... \\
        2: & 1 & 2 & 1 & 0 & 0 & 0 &... \\
        3: & 1 & 3 & 3 & 1 & 0 & 0 &... \\
        4: & 1 & 4 & 6 & 4 & 1 & 0 &... \\
        5: & 1 & 5 & 10& 10& 5 & 1 &... \\
        ...&...&...&...&...&...&...&... \\
    \end{array}
</math>
 
There is an infinity of <math>\scriptstyle 1</math> and <math>\scriptstyle -1</math>. This is another hint that this object is a matrix. Each term in this row obeys the addition rule and the row rule. Some calculations should convince you.


Up until now, we added along the rows and the columns. We can add along the diagonals. Adding from left to right gives :
We can further extend the triangle along the negative axis.


<math>
    \begin{array}{rrrrrrrrr}
        ...&...&...&...&...&...&...&...&... \\
      -4: & 1 & -4& 10&-20& 35&-56& 84&... \\
      -3: & 1 & -3& 6 &-10& 15&-21& 28&... \\
      -2: & 1 & -2& 3 & -4& 5 &-6 & 7 &... \\
      -1: & 1 & -1& 1 & -1& 1 &-1 & 1 &... \\
        0: & 1 & 0 & 0 & 0 & 0 & 0 & 0 &... \\
        1: & 1 & 1 & 0 & 0 & 0 & 0 & 0 &... \\
        2: & 1 & 2 & 1 & 0 & 0 & 0 & 0 &... \\
        3: & 1 & 3 & 3 & 1 & 0 & 0 & 0 &... \\
        4: & 1 & 4 & 6 & 4 & 1 & 0 & 0 &... \\
        5: & 1 & 5 & 10& 10& 5 & 1 & 0 &... \\
        ...&...&...&...&...&...&...&...&... \\
    \end{array}
</math>
As we wrote earlier, Newton did not stop there. He asked himself if there were rows with fractional index, like <math>\scriptstyle \frac{1}{2}</math>. And the answer is yes !
In the preceding example, we computed the terms of row 4. Let's use that row again :


<math>
<math>
     \begin{array}{ccccccccccr}
     \begin{array}{lcccccc}
        1 &   &   &   &   &  &  &  &  & = & 1  \\
      4: & 1 & 4 & 6 & 4 & 1 & \\
         1 &   &   &   &   &   &   &   &   & = & 1  \\
    \end{array}
        1 & + & 1 &   &   &   &   &   &   & = & 2  \\
</math>
        1 & + & 2 &   &   &   &   &   &   & = & 3  \\
 
        1 & + & 3 & + & 1 &   &   &   &   & = & 5  \\
 
         1 & + & 4 & + & 3 &   &   &   &   & = & 8 \\
:<math> \scriptstyle 1 \times \frac{4 - 0}{1 + 0} = 4~</math>
         1 & + & 5 & + & 6 & + & 1 &   &   & = & 13 \\
 
         1 & + & 6 & + &10 & + & 4 & + & 1 & = & 21 \\
:<math> \scriptstyle 4 \times \frac{4 - 1}{1 + 1} = 6~</math>
      ...&   &   &   &   &   &   &   &  & = &... \\
 
:<math> \scriptstyle 6 \times \frac{4 - 2}{1 + 2} = 4~</math>
 
:<math> \scriptstyle \cdots ~</math>
 
What is the first term of row <math>\scriptstyle \frac{1}{2}</math>? By definition, it is 1. What are the terms after that ? We will use the row rule to compute them !
 
:<math> \scriptstyle 1            \times \frac{\frac{1}{2} - 0}{1 + 0} = \frac{1}{2} ~</math>
 
:<math> \scriptstyle \frac{1}{2} \times \frac{\frac{1}{2} - 1}{1 + 1} = -\frac{1}{8} ~</math>
 
:<math> \scriptstyle -\frac{1}{8} \times \frac{\frac{1}{2} - 2}{1 + 2} = \frac{1}{16} ~</math>
 
:<math> \scriptstyle \frac{1}{16} \times \frac{\frac{1}{2} - 3}{1 + 3} = -\frac{5}{128} ~</math>
 
:<math> \scriptstyle \cdots ~</math>
 
No term goes to zero, even if each comes closer as it is further away from the first.
 
In the following Bernoulli triangle, using the row rule, we added the rows <math>\scriptstyle \frac{1}{2}</math> and <math>\scriptstyle \frac{3}{2}</math> :
 
<math>
    \begin{array}{rrrrrrrrr}
         ...&...&...&...&...&...&...&...&...\\
      -4: & 1 &-4 &10 &-20&35 &-56&84 &...\\
      -3: & 1 &-3 & 6 &-10&15 &-21&28 &...\\
      -2: & 1 &-2 & 3 & -4& 5 &-6 & 7 &...\\
      -1: & 1 &-1 & 1 & -1& 1 &-1 & 1 &...\\
         0: & 1 & 0 & 0 & 0 & 0 & 0 & 0 &...\\
        \frac{1}{2}: & 1 & \frac{1}{2} & -\frac{1}{8} & \frac{1}{16} & -\frac{5}{128} &\frac{7}{256} &-\frac{21}{1024} &...\\
         1: & 1 & 1 & 0 & 0 & 0 & 0 & 0 &...\\
        \frac{3}{2}: & 1 & \frac{3}{2} & \frac{3}{8} & -\frac{1}{16} & \frac{3}{128} &-\frac{3}{256}&\frac{7}{1024}&...\\
         2: & 1 & 2 & 1 & 0 & 0 & 0 & 0 &...\\
        3: & 1 & 3 & 3 & 1 & 0 & 0 & 0 &...\\
        ...&...&...&...&...&...&...&...&...\\
     \end{array}
     \end{array}
</math>
</math>


Some calculations confirm that the addition rule works, as expected. After some tests, we see that it works only if the row indices have a difference of 1. For instance, we cannot easily build row 3.25 from row 3, but we can easily build row <math>\scriptstyle \frac{3}{2}</math> from row <math>\scriptstyle \frac{1}{2}</math>. Up to a point, there are two matrices in the preceding Bernoulli triangle, one for the integers and one for the multiples of <math>\scriptstyle \frac{1}{2}</math>.
Newton's generalizations opened routes to areas not primarily connected to [[integer]]s, namely [[nth root|numeric root]]s (like the [[square root]]s) and [[logarithm]]s.
== Computing a Root Square ==
Armed with the knowledge of the previous section, we are ready to compute the [[square root]] of a number.
We start with this equation :
:<math>(x+y)^2 = x^2 + 2 x y + y^2~</math>,
If we replace <math>x~</math> with 2 and <math>y~</math> with 3, then we get
:<math>(2+3)^2 = 2^2 + 2 \times 2 \times 3 + 3^2~</math>,
which is equal to 25, or <math>(2 + 3)^2 = 5^2~</math>. This is quite common knowledge, not to say boring.
Suppose we replace the exponent 2, an [[integer]], by the exponent <math>\frac{1}{2}~</math>, a fraction. When the exponent value is 2, we get the square, when it is <math>\frac{1}{2}~</math>, we get the square root. This a rule of the [[exponentiation]]. Thus, we can use the triangle's terms to compute a square root.
This observation is technically correct, but there are some details that hugely simplify the calculations. If the exponent is a fraction, then <math>x~</math> SHOULD be equal to 1 and, in this case, <math>y~</math> MUST be equal to or less than 1. More precisely, <math>|y| < 1~</math><ref>The reason of this limitation is outside the scope of this article, it has to do with [[series]] convergence.</ref>.
Let's compute <math>(2+3)^{\frac{1}{2}}~</math>, i.e. <math>\sqrt{5}~</math>.
<math>
    (2+3)^{\frac{1}{2}}
        = (4 + 1)^{\frac{1}{2}}
        = (4 \times (1 + \frac{1}{4}))^{\frac{1}{2}}
        = 4^{\frac{1}{2}} \times (1 + \frac{1}{4})^{\frac{1}{2}}
        = 2 \, (1 + 0.25)^{\frac{1}{2}}
</math>
In the last parenthesis, <math>x~</math> is equal to 1, and <math>|y| = 0.25~</math> is lower than 1. Here is how we proceeded. Compute the perfect square lower than <math>(2 + 3)~</math>, here it is 4. Change the sum within the parenthesis in order to display the perfect square. Get it outside the parenthesis, while applying the square root operation on both terms. Extract the square root from both, one requiring to use the binomial coefficients.
To compute the root square of the parenthesis, we use the row <math>{\frac{1}{2}}~</math> in the triangle.
<math>
    (1 + 0.25)^{\frac{1}{2}}
        = 1 + \frac{1}{2} \times 0.25
            - \frac{1}{8} \times 0.25^2+ 
            \cdots
</math>
<math>
    (1 + 0.25)^{\frac{1}{2}}
        \approx 1 +  \frac{1}{2} \times 0.25
            - \frac{1}{8} \times 0.25^2=1.1171875
</math>
Using three terms, the square root estimate of <math>(2 + 3)~</math> is <math>2 * 1.1171875 = 2.234375</math>. The square of this value is <math>4.9924316\dots</math>. Compared to the exact value, the error of calculating square root is close to 0.1%. Using more terms will sharpen the result.
We can compute any root with this method. However, it is not used in practice, since there are faster convergent methods, like the [[Newton-Raphson algorithm]].
== Computing the Logarithm of a Number ==
Starting with this equation :
:<math>(x+y)^2 = x^2 + 2 x y + y^2~</math>,
we replace some terms within it :
:<math>(1+z)^2 = 1^2 + 2 \times 1 \times z + z^2~</math>
:<math>(1+z)^2 = 1 + 2 z + z^2~</math>,
which is good for the square of <math>(1+z)~</math>. To compute the [[logarithm]], we use the terms in row -1.
:<math>(1+z)^{-1} = 1 - z + z^2 - z^3 + z^4 - z^5 + z^6 +\cdots~</math>
If we [[integration|integrate]] both sides of the previous equation<ref>From [[calculus]], we know that :
:<math> \scriptstyle \cdots~</math>
:<math> \scriptstyle \int{z^1 dz}= \frac{z^2}{2} + C,\,\,C\,\hbox{is an arbitrary constant}~</math>
:<math> \scriptstyle \int{z^0 dz}= \frac{z^1}{1} + C~</math>
:<math> \scriptstyle \int{z^{-1} dz} = \int{\frac{dz}{z} } = \ln{z} + C~</math>
:<math> \scriptstyle \int{z^{-2} dz} = \frac{z^{-1}}{-1} + C~</math>
:<math> \scriptstyle \int{z^{-3} dz} = \frac{z^{-2}}{-2} + C ~</math>
:<math> \scriptstyle \cdots~</math></ref>, we get the natural logarithm of a number<ref>William H Beyer (ed.), ''Standard Mathematical Tables and Formulae, 29th edition'', CRC Press, p.279. ISBN 0-8493-0629-9</ref> :
:<math>\ln{(1+z)} = z - \frac{z^2}{2} + \frac{z^3}{3} - \frac{z^4}{4} + \frac{z^5}{5} - \frac{z^6}{6} + \frac{z^7}{7} +\cdots \text{ with } z \in \R \text{ and } -1 < z \leq 1 ~</math>
== Matrix Exponential ==
At the beginning of the 21st century, someone found a remarkable equality between the Pascal's triangle and a [[power series]] of square [[matrix|matrices]].<ref>For instance, see Gottfried Helms, [http://go.helms-net.de/math/pdf/PascalDreieckMatrixLog.pdf "Some Properties of the Binomial-("Pascal"-)-triangular matrix"], 2005-08-31, version 3.</ref>
As you probably know, we can compute the [[exponential function]] like this : <math> \scriptstyle e^x = \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \cdots </math> Moreover, maybe you remember that we can multiply a square matrix <math>\scriptstyle a_{{nn}}</math> of rank <math>\scriptstyle n</math> with any other square matrix of the same rank. Combining these two facts, we get
<math> e^{{a_{{nn}}}} = \frac{({{a_{{nn}}}})^0}{0!} + \frac{({{a_{{nn}}}})^1}{1!} + \frac{({{a_{{nn}}}})^2}{2!} + \cdots </math>
We are ready to compute the figurate number triangle of order 3 :
<math>e^{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      1 & 0& 0 \\
      0 & 2& 0 \\
    \end{array} \right]} = \frac{{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      1 & 0& 0 \\
      0 & 2& 0 \\
    \end{array} \right]}^0}{0!} + \frac{{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      1 & 0& 0 \\
      0 & 2& 0 \\
    \end{array} \right]}^1}{1!} + \frac{{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      1 & 0& 0 \\
      0 & 2& 0 \\
    \end{array} \right]}^2}{2!} + \cdots </math>
<math>e^{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      1 & 0& 0 \\
      0 & 2& 0 \\
    \end{array} \right]} = \frac{{\left[ \begin{array}{ccc}
      1 & 0& 0 \\
      0 & 1& 0 \\
      0 & 0& 1 \\
    \end{array} \right]}}{1} + \frac{{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      1 & 0& 0 \\
      0 & 2& 0 \\
    \end{array} \right]}}{1} + \frac{{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      0 & 0& 0 \\
      2 & 0& 0 \\
    \end{array} \right]}}{2} + \cdots </math>
<math>e^{\left[ \begin{array}{ccc}
      0 & 0& 0 \\
      1 & 0& 0 \\
      0 & 2& 0 \\
    \end{array} \right]} = \left[ \begin{array}{ccc}
      1 & 0& 0 \\
      1 & 1& 0 \\
      1 & 2& 1 \\
    \end{array} \right] </math>
To get bigger figurate number triangles, use bigger square matrices, filling the subdiagonal under the main diagonal with <math>\scriptstyle 1, 2, 3, \cdots</math>, the rest is set to zero.
In [[combinatorics]], the Pascal's triangle is simply defined by <math>\scriptstyle \binom{n}{k} = \frac{n!}{k!(n-k)!}</math> with <math>\scriptstyle k, n \in \N</math>. This compact equation provides the basis for many identities. However, it is not easy to manipulate through [[function]]s. The matrix exponential opens new territories, since it gives a new way to manipulate the triangle using results from the [[matrix theory]] and the function theory. For instance, is the triangle a solution of <math> \scriptstyle x^2 + 3x - 4I = 0 </math> ? What is its inverse ? What is its logarithm ?
== Normal Curve ==
Pascal's triangle lends itself to graphical representation. If you draw an histogram of the 19th row, you would get something like the following picture.
{{Image|Pascal's Triangle, Histogram of binomial coefficients at row 19.png|center|300px|Histogram of the 19th row within the Pascal's triangle}}
Suppose we compute the terms of the 1000th row in Pascal's triangle. If we divide each term by 2<sup>1000</sup> and consider each value as a point on a ''continuous'' curve, we would get the following curve.
[[Image:Pascal's Triangle, Normal Curve.png|center|thumb|300px|The [[Normal distribution|normal curve]], a limit case of any high-order row within the Pascal's Triangle.]]
[[Carl Friedrich Gauss|Gauss]], the famous German mathematician, studied the [[Normal distribution|normal curve]]<ref name="boursin">{{fr}} Jean-Louis Boursin, ''Les Structures du hasard'', Seuil, coll. Les Rayons de la science, 1966, p.129.</ref>. It is the commonest [[statistics|statistical]] law encountered in natural phenomenons<ref name="boursin"/><ref>Paul Westbrook, ''Math Smart for Business: Cultivating a Six-Figure Vocabulary'', Princeton Review, 1997, p. 70. ISBN 0679783911. Consulted 2007-11-19. View an extract at [http://books.google.com/books?id=viAvQxqSMPAC&pg=PA70&lpg=PA70&dq=%22normal+curve%22+statistics+%22most+common+curve%22&source=web&ots=3-VbF7Y-KP&sig=HEJAwB8Ct5KTb1aWG8usApJU5Go].</ref>. For this reason, the properties of many statistical curves are compared to the normal curve properties. In its simplest form, its equation is <math>\scriptstyle P(z) = e^{-z^2/2}</math>.
== Identities ==
We already presented some useful equations for building the Pascal's triangle. Since they are true within a [[field]] (a commutative [[Ring (mathematics)|ring]]), they are called [[identity|identities]] in mathematics. Below, we list some more, but be aware there are literaly thousands of them.
'''1.'''
For <math> \scriptstyle x, y \in \R</math> and <math> \scriptstyle n \in \N </math>,
<math>
      (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}
</math>
with
<math> \binom{n}{k} = \frac{n!}{k!(n-k)!} </math>
'''2.'''
For <math> \scriptstyle n \in \N</math>,
<math>
    \sum_{k=0}^n \binom{n}{k} = 2^n
</math>
   
'''3.'''
For <math> \scriptstyle n \in \N</math>,
<math>
    \sum_{k=0}^n (-1)^k \binom{n}{k} = 0
</math>
   
'''4.'''
For <math> \scriptstyle n \in \N</math>,
<math>
    \sum_{k=0}^n 2^k \binom{n}{k} = 3^n
</math>
'''5.'''
(''Pascal's identity'') For <math> \scriptstyle n \in \N</math>,
<math>
      \binom{n + 1}{k} = \binom{n}{k - 1} + \binom{n}{k}
</math>
'''6.'''
(''Vandermonde's identity'') For <math> \scriptstyle m, n, r \in \N^+</math>, <math> \scriptstyle r \le m</math>, <math> \scriptstyle r \le n</math>,
<math>
      \binom{m + n}{r} = \sum_{k=0}^r \binom{m}{r - k} \binom{n}{k}
</math>
'''7.'''
For <math> \scriptstyle n \in \N</math>,
<math>
      \binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2
</math>
'''8.'''
For <math> \scriptstyle n, r \in \N^+</math>, <math> \scriptstyle r \le n</math>,
<math>
      \binom{n + 1}{r + 1} = \sum_{j=r}^n \binom{j}{r}
</math>
The previous identities remain true if the variables are complex (e.g., <math> \scriptstyle (3 - 7 i)</math>). Some identities relating to Pascal's triangle are true when <math> \scriptstyle m</math>, <math> \scriptstyle n</math>, and <math> \scriptstyle r</math> are fractional.


The numbers on the rigth are the [[Fibonacci number]]s.
'''9.''' ('' Newton's identity'') For <math> \scriptstyle x, y \in \R</math> and <math> \scriptstyle r \in \R</math>,
 
<math>
        (x+y)^r=\sum_{k=0}^\infty \binom{n}{k} x^k y^{r-k}
</math>
   
with
 
<math>
\binom{n}{k} = \frac{1}{k!} \prod_{i=0}^{n-1}(n-k)
            = \frac{n(n-1)\cdots(n-k+1)}{k!}
</math>
   
When <math> \scriptstyle r</math> is an integer, we fall back on the first identity. The number of terms is still infinite, but almost all of them are equal to zero (those in the tail).
 
== Unexpected Relations ==
; Prime number multiples
Ones excepted, all the terms in any row where the second term is a [[prime number]] are multiple of the prime number. For instance, if a row starts with <math>\scriptstyle 1, 23, 253, \cdots </math>, then all its terms, ones excepted, are multiple of 23.<ref>See [http://binomial.csuhayward.edu/Identities.html#5.1 ''Pascal's Triangle From Top to Bottom''], California State University, East Bay. Consulted 2007-11-28.</ref>
 
; Odd numbers within a row
Each row of order <math>\scriptstyle 2^n-1, n \in \N</math>, only contains odd numbers. No other row has this property.
 
; <math>\scriptstyle \pi </math> and <math>\scriptstyle e </math>
We saw the normal curve, a way to represent the binomial coefficients as a continuous curve. In its simplest form, its equation <math>\scriptstyle P(z) = e^{- z^2/2}</math> and the area under that curve is <math>\scriptstyle \sqrt{2 \pi}</math>. The equation of this curve involves <math>\scriptstyle e</math>, while its area involves <math>\scriptstyle \pi</math>. How can this be possible, since the binomial coefficients are obtained by adding natural numbers, and we divided those coefficients by a power of 2 ?
 
; Constructible polygons
Applying modulo 2 to every number in Pascal's triangle, we get
<center>
<code>
1
 
1 1
 
1 0 1
 
1 1 1 1
 
1 0 0 0 1
 
1 1 0 0 1 1
 
1 0 1 0 1 0 1
 
...
</code>
</center>
 
Viewing these ones and zeroes as binary digits, we get 1, 3, 5, 15, 17, 51,... in base ten. They are the number of sides found in constructible [[polygon]]s with odd number of sides. This is true up to row 32.<ref>Eric W. Weisstein, ''CRC Concise Encyclopedia of Mathematics'', CRC Press, 1999, p. 1399. ISBN 0-8493-9640-9</ref>
 
; Computing <math>\scriptstyle \pi </math>
We can compute <math>\scriptstyle \pi</math> from the Pascal's triangle : <math>\scriptstyle \frac{\binom{2n}{n}}{2^{2n}} = \frac{1}{\sqrt{n \pi}}</math>. For instance,
<math>\scriptstyle \frac{\binom{50}{25}}{2^{50}} = \frac{1}{\sqrt{25 \pi}}</math>
outputs <math>\scriptstyle \pi = 3.17316</math>. This formula is not used in
practice since <math>\scriptstyle n</math> must be very large to compute <math>\scriptstyle \pi</math> to any decent precision.
 
; Stacking marbles
If you stack marbles in the simplest 1D figure (along a line), then you arrange 1, 2, 3, 4,... marbles.
If you stack marbles in the simplest 2D figure (triangle), then you arrange 1, 3, 6, 10,... marbles.
If you stack marbles in the simplest 3D figure (a tetrahedron or 4-sided pyramid), then you arrange 1, 4, 10, 20,... marbles.
If you stack marbles in the simplest 4D figure (a 4-simplex), then you arrange 1, 5, 15, 35,... marbles.
And so on.
 
These numbers appear within the columns of the figurate number triangle,
the column 1 contains the classic and basic counting numbers : 1, 2, 3, 4,...
The column 2 contains the triangular numbers : 1, 3, 6, 10, 15, 21,...
The column 3 contains the tetrahedral numbers : 1, 4, 10, 20, 35, 56,...
The column 4 contains the pentatope numbers : 1, 5, 15, 35, 70, 126,...
And so on.
 
; Catalan numbers
The Pascal's triange hides the [[Catalan number]]s.
 
<center>
<code>
<u>1</u>
 
1 1
 
1 <u>2</u> 1
 
1 3  3 1
 
1 4  <u>6</u>  4 1
 
1 5 10 10 5 1
 
1 6 15 <u>20</u> 15 6 1
 
1 7 21 35 35 21 7 1
 
1 8 28 56 <u>70</u> 56 28 8 1
 
...
</code>
</center>
 
Dividing the underlined numbers by 1, 2, 3, 4,..., we get 1, 1, 2, 5, 14,... The Catalan numbers appear in solutions of many combinatorial problems.<ref>Eric W. Weisstein, ''CRC Concise Encyclopedia of Mathematics'', CRC Press, 1999, p. 200. ISBN 0-8493-9640-9</ref> There is another way to compute these numbers : in the triangle, subtract the neighbour from each underlined number.
 
There is a surprising way to compute them. Square the terms in each row and add them :
 
<math> \scriptstyle 1^2 = 1 </math>
 
<math> \scriptstyle 1^2 + 1^2 = 2 </math>
 
<math> \scriptstyle 1^2 + 2^2 + 1^2 = 6 </math>
 
<math> \scriptstyle 1^2 + 3^2 + 3^2 + 1^2 = 20 </math>
 
<math> \scriptstyle 1^2 + 4^2 + 6^2 + 4^2 + 1^2 = 70 </math>
 
<math> \scriptstyle ... </math>
 
These are the underlined values in the previous triangle.
 
; Geometric counting
Somebody found a strange property relating geometry to the numbers within the Pascal's triangle.
 
A dot has one vertex (1).
A segment has two vertices and one line (2,1).
A triangle has three vertices, three edges and one surface (3, 3, 1).
A triangular pyramid has four vertices, six edges, four surfaces and one volume (4, 6, 4, 1).
And so on. Thus, the element count of a minimal regular geometric object (build from regular shapes) in 1D, 2D, 3D, 4D, etc., is specified by a row in the Pascal's triangle.
 
; Bernoulli numbers
[[Bernoulli number]]s, named in honor of [[Jacob Bernoulli]] who studied them intensively, arise in a wide variety of analytical and combinatorial contexts. They are<ref>William H Beyer (ed.), ''Standard Mathematical Tables and Formulae'', 29th edition, CRC Press, p.394. ISBN 0-8493-0629-9</ref>
 
<math> \scriptstyle B_0 = 1, \, B_1 = \frac{1}{2}, \, B_2 = \frac{1}{6}, \, B_3 = B_5 = B_7 = ... = 0 </math>
 
<math> \scriptstyle B_4 = -\frac{1}{30}, \, B_6 = \frac{1}{42}, \, B_8 = -\frac{1}{30}, \, B_{10} = \frac{5}{66}, ... </math>
 
Knowing that <math> \scriptstyle B_0</math> and <math> \scriptstyle B_1</math> are the two first terms of this series, we can compute all the terms :
 
<math> \scriptstyle B_0 = 1</math>, then <math> \scriptstyle B_0 = 1 </math>
 
<math> \scriptstyle B_1 - B_0 = -1/2</math>, then <math> \scriptstyle B_1 = 1/2 </math>
 
<math> \scriptstyle B_2 - 2 B_1 + B_0 = B_2</math>, then <math> \scriptstyle B_1 = 1/2 </math>
 
<math> \scriptstyle B_3 - 3 B_2 + 3 B_1 - B_0 = B_3</math>, then <math> \scriptstyle B_2 = 1/6 </math>
 
<math> \scriptstyle B_4 - 4 B_3 + 6 B_2 - 4 B_1 + B_0 = B_4</math>, then <math> \scriptstyle B_3 = 0 </math>
 
<math> \scriptstyle B_5 - 5 B_4 + 10 B_3 - 10 B_2 + 5 B_1 - B_0 = B_5</math>, then <math> \scriptstyle B_4 = -1/30 </math>
 
<math> \scriptstyle ... </math>
 
<math> \scriptstyle B_1</math> is computed twice, but this arrangement clearly shows the binomial coefficients.<ref>Eric W. Weisstein, ''CRC Concise Encyclopedia of Mathematics'', CRC Press, 1999, p. 112. ISBN 0-8493-9640-9</ref>


== References ==
== References ==
<References/>
{{reflist|2}}[[Category:Suggestion Bot Tag]]
 
[[Category:CZ Live]]

Latest revision as of 16:01, 1 October 2024

This article is a stub and thus not approved.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
https://en.citizendium.org/wiki/index.php?title=Pascal%27s_triangle&printable=yes
This editable Main Article is under development and subject to a disclaimer.

Pascal's triangle is a convenient tabular representation of the binomial coefficients. Already known in the 11th century,[1] it was adopted in the Western world under this name after Blaise Pascal published his Traité du triangle arithmétique ("Treatise on the Arithmetical Triangle") in 1654.

Pascal's triangle appears under different formats. Here is its most common:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{cccccccccccc} & & & & & & 1 & & & & & \\ & & & & & 1& & 1 & & & & \\ & & & & 1 & & 2 & & 1 & & & \\ & & & 1 & & 3& & 3& & 1 & & \\ & & 1 & & 4 & & 6 & & 4 & & 1 & \\ & 1 & & 5 & & 10& & 10& & 5 & & 1 \\ & & & & & &\cdots&& & & & \end{array} }

We can use Pascal's triangle to compute the binomial expansion of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle (x + y)^n} . For instance,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+y)^4 = 1 \times x^4 + 4 \times x^3y + 6 \times x^2y^2 + 4 \times xy^3 + 1 \times y^4 }

The triangle shows the coefficients Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1, 4, 6, 4, 1} on the fifth row.

Pascal's triangle has applications in algebra and in probabilities. We can use it to compute the Fibonacci numbers and to create the Sierpinski triangle. After studying it, Isaac Newton expanded the triangle and found new methods to extract the square root and to calculate the natural logarithm of a number.

History

Drawing of Pascal's Triangle published in 1303 by Zhu Shijie (1260-1320), in his Si Yuan Yu Jian. It was called Yanghui Triangle by the Chinese, after the mathematician Yang Hui.
The fourth entry from the left in the second row from the bottom appears to be a typo (34 instead of 35, correctly given in the fifth entry in the same row).

The earliest explicit depictions of a triangle of binomial coefficients occur in the 10th century in commentaries on the Chandas Shastra, an ancient Indian book on Sanskrit prosody written by Pingala between the 5th century BC and 2nd century BC. While Pingala's work only survives in fragments, the commentator Halayudha, around 975, used the triangle to explain obscure references to Meru-prastaara, the "Staircase of Mount Meru". It was also realised that the shallow diagonals of the triangle sum to the Fibonacci numbers. The Indian mathematician Bhattotpala (c. 1068) later gives rows 0-16 of the triangle.

At around the same time, it was discussed in Persia by the mathematician Al-Karaji (953–1029) and the poet-astronomer-mathematician Omar Khayyám (1048-1131); thus the triangle is referred to as the "Khayyam triangle" in Iran. Several theorems related to the triangle were known, including the binomial theorem. It seems that Khayyam used a method of finding nth roots based on the binomial expansion, and therefore on the binomial coefficients.

In 13th century, Yang Hui (1238-1298) presented an arithmetic triangle, which was the same as Pascal's Triangle. Today, Pascal's triangle is called "Yang Hui's triangle" in China. In Italy, it is known as "Tartaglia's triangle", named for the Italian algebraist Niccolo Fontana Tartaglia who lived a century before Pascal.

In 1655, Blaise Pascal published its Traité du triangle arithmétique ("Treatise on arithmetical triangle"), wherein he collected several results then known about the triangle, and employed them to solve problems in probabilities. The triangle was later named after Pascal by Pierre Raymond de Montmort (1708) and Abraham de Moivre (1730).

After that, even if it was useful in many areas of mathematics, most research was done within its descendants, like probabilities and combinatorics.

Some Properties

Each term in the triangle is the sum of the two terms above it[2]. For instance, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 6 = 3 + 3} . The binomial coefficients relate to this construction by Pascal's rule, which states that if

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n \choose k} = \frac{n!}{k! (n-k)!} }

is the kth binomial coefficient in the binomial expansion of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle (x + y)^n} , then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} \text{ with } k, n \in \N^* \text{ and } 0 \leq k \leq n }

By convention, the binomial coefficient Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle {n \choose k}} is set to zero if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle k} is either less than zero or greater than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n} .

To better understand some properties, the triangle is presented differently :


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{cccccccc} 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 \\ ...&...&...&...&...&...&...&...\\ \end{array} }

Each coefficient is the sum of the coefficient exactly over it and its left neighbour[2]. For instance, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 3 + 3 = 6} . Let's call this rule the "addition rule".

Using this format, it is easy to apply an index to each row :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lcccccccc} 0: & 1 & & & & & & & \\ 1: & 1 & 1 & & & & & & \\ 2: & 1 & 2 & 1 & & & & & \\ 3: & 1 & 3 & 3 & 1 & & & & \\ 4: & 1 & 4 & 6 & 4 & 1 & & & \\ 5: & 1 & 5 & 10& 10& 5 & 1 & & \\ 6: & 1 & 6 & 15& 20& 15& 6 & 1 & \\ 7: & 1 & 7 & 21& 35& 35& 21& 7 & 1 \\ ...&...&...&...&...&...&...&...&...\\ \end{array} }

Starting the indices at zero facilitates many calculations.

The sum of any row is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 2^r} , with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle r} being the row index : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 0, 1, 2, \ldots} For instance, the sum of row 4 is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1 + 4 + 6 + 4 + 1 = 16 = 2^4} .

Since there is a formula for summing a row, then maybe there is one for a column ? It is the case. This time, we index the columns :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lcccccccc} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0: & 1 & & & & & & & \\ 1: & 1 & 1 & & & & & & \\ 2: & 1 & 2 & 1 & & & & & \\ 3: & 1 & 3 & 3 & 1 & & & & \\ 4: & 1 & 4 & 6 & 4 & 1 & & & \\ 5: & 1 & 5 & 10& 10& 5 & 1 & & \\ 6: & 1 & 6 & 15& 20& 15& 6 & 1 & \\ 7: & 1 & 7 & 21& 35& 35& 21& 7 & 1 \\ ...&...&...&...&...&...&...&...&...\\ \end{array} }

Anyone familiar with the factorial function can easily find the general formula. The sum of a column Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle c} ending at row Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle r} is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{(r+1) \times r \, \times \cdots \times (r-c+1)}{(c + 1)!} \text{ with } r, c \in \N^*} .

There is another method to compute this sum, see [3].

Up until now, we added along the rows and the columns. We can add along the diagonals. Doing so from left to right and from bottom to top gives :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{ccccccccccr} 1 & & & & & & & = & 1 \\ 1 & & & & & & & = & 1 \\ 1 & + & 1 & & & & & = & 2 \\ 1 & + & 2 & & & & & = & 3 \\ 1 & + & 3 & + & 1 & & & = & 5 \\ 1 & + & 4 & + & 3 & & & = & 8 \\ 1 & + & 5 & + & 6 & + & 1 & = & 13 \\ 1 & + & 6 & + &10 & + & 4 & = & 21 \\ ...& & & & & & & = &... \\ \end{array} }

The numbers on the right are the Fibonacci numbers.

One Row at a Time

We can build any row if we know the row before just by adding its terms two at a time. However, it is possible to build a row directly. We will build the row 4 in order to discover the rule. Each row starts with 1 :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lcccccc} 4: & 1 & 4 & 6 & 4 & 1 & \\ \end{array} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1 \times \frac{4 - 0}{1 + 0} = 4 ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 4 \times \frac{4 - 1}{1 + 1} = 6 ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 6 \times \frac{4 - 2}{1 + 2} = 4 ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 4 \times \frac{4 - 3}{1 + 3} = 1 ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1 \times \frac{4 - 4}{1 + 4} = 0 ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \cdots ~}


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{r}{c + 1} = \binom{r}{c} \times \frac{r - c}{1 + c} \text{ with } r, c \in \N^* \text{ and } r \ge c ~} [4]

Once the row and the column indices are know, we can compute the neighbours, either right or left, of any term. Because it only applies to a row, we call it the "row rule".

Polynomials with coefficients in triangle

Newton's Binomial Coefficients

Isaac Newton studied the triangle's properties and discovered two remarkable generalizations.[5]

He extended the triangle along the negative axis. To better understand how he achieved this, let us write the triangle using another format :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lccccccccc} 0: & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ... \\ 1: & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & ... \\ 2: & 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & ... \\ 3: & 1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & ... \\ 4: & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 & ... \\ 5: & 1 & 5 & 10& 10& 5 & 1 & 0 & 0 & ... \\ 6: & 1 & 6 & 15& 20& 15& 6 & 1 & 0 & ... \\ 7: & 1 & 7 & 21& 35& 35& 21& 7 & 1 & ... \\ ...&...&...&...&...&...&...&...&...& ... \\ \end{array} }

Jacob Bernoulli is the "father" of this mathematical object named the "figurate number triangle"[6]. To ease the understanding in the following text, we will call it the "Bernoulli triangle", even if this matrix does not resemble a triangle anymore !

Using the row rule, let's compute the row -1 :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{rrrrrrrr} -1: & 1 & -1& 1 & -1& 1 &-1 &... \\ 0: & 1 & 0 & 0 & 0 & 0 & 0 &... \\ 1: & 1 & 1 & 0 & 0 & 0 & 0 &... \\ 2: & 1 & 2 & 1 & 0 & 0 & 0 &... \\ 3: & 1 & 3 & 3 & 1 & 0 & 0 &... \\ 4: & 1 & 4 & 6 & 4 & 1 & 0 &... \\ 5: & 1 & 5 & 10& 10& 5 & 1 &... \\ ...&...&...&...&...&...&...&... \\ \end{array} }

There is an infinity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle -1} . This is another hint that this object is a matrix. Each term in this row obeys the addition rule and the row rule. Some calculations should convince you.

We can further extend the triangle along the negative axis.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{rrrrrrrrr} ...&...&...&...&...&...&...&...&... \\ -4: & 1 & -4& 10&-20& 35&-56& 84&... \\ -3: & 1 & -3& 6 &-10& 15&-21& 28&... \\ -2: & 1 & -2& 3 & -4& 5 &-6 & 7 &... \\ -1: & 1 & -1& 1 & -1& 1 &-1 & 1 &... \\ 0: & 1 & 0 & 0 & 0 & 0 & 0 & 0 &... \\ 1: & 1 & 1 & 0 & 0 & 0 & 0 & 0 &... \\ 2: & 1 & 2 & 1 & 0 & 0 & 0 & 0 &... \\ 3: & 1 & 3 & 3 & 1 & 0 & 0 & 0 &... \\ 4: & 1 & 4 & 6 & 4 & 1 & 0 & 0 &... \\ 5: & 1 & 5 & 10& 10& 5 & 1 & 0 &... \\ ...&...&...&...&...&...&...&...&... \\ \end{array} }

As we wrote earlier, Newton did not stop there. He asked himself if there were rows with fractional index, like Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{1}{2}} . And the answer is yes !

In the preceding example, we computed the terms of row 4. Let's use that row again :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lcccccc} 4: & 1 & 4 & 6 & 4 & 1 & \\ \end{array} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1 \times \frac{4 - 0}{1 + 0} = 4~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 4 \times \frac{4 - 1}{1 + 1} = 6~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 6 \times \frac{4 - 2}{1 + 2} = 4~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \cdots ~}

What is the first term of row Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{1}{2}} ? By definition, it is 1. What are the terms after that ? We will use the row rule to compute them !

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1 \times \frac{\frac{1}{2} - 0}{1 + 0} = \frac{1}{2} ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{1}{2} \times \frac{\frac{1}{2} - 1}{1 + 1} = -\frac{1}{8} ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle -\frac{1}{8} \times \frac{\frac{1}{2} - 2}{1 + 2} = \frac{1}{16} ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{1}{16} \times \frac{\frac{1}{2} - 3}{1 + 3} = -\frac{5}{128} ~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \cdots ~}

No term goes to zero, even if each comes closer as it is further away from the first.

In the following Bernoulli triangle, using the row rule, we added the rows Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{1}{2}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{3}{2}}  :

Some calculations confirm that the addition rule works, as expected. After some tests, we see that it works only if the row indices have a difference of 1. For instance, we cannot easily build row 3.25 from row 3, but we can easily build row from row . Up to a point, there are two matrices in the preceding Bernoulli triangle, one for the integers and one for the multiples of .

Newton's generalizations opened routes to areas not primarily connected to integers, namely numeric roots (like the square roots) and logarithms.

Computing a Root Square

Armed with the knowledge of the previous section, we are ready to compute the square root of a number.

We start with this equation :

,

If we replace with 2 and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y~} with 3, then we get

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2+3)^2 = 2^2 + 2 \times 2 \times 3 + 3^2~} ,

which is equal to 25, or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2 + 3)^2 = 5^2~} . This is quite common knowledge, not to say boring.

Suppose we replace the exponent 2, an integer, by the exponent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{2}~} , a fraction. When the exponent value is 2, we get the square, when it is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{2}~} , we get the square root. This a rule of the exponentiation. Thus, we can use the triangle's terms to compute a square root.

This observation is technically correct, but there are some details that hugely simplify the calculations. If the exponent is a fraction, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x~} SHOULD be equal to 1 and, in this case, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y~} MUST be equal to or less than 1. More precisely, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |y| < 1~} [7].

Let's compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2+3)^{\frac{1}{2}}~} , i.e. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{5}~} .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2+3)^{\frac{1}{2}} = (4 + 1)^{\frac{1}{2}} = (4 \times (1 + \frac{1}{4}))^{\frac{1}{2}} = 4^{\frac{1}{2}} \times (1 + \frac{1}{4})^{\frac{1}{2}} = 2 \, (1 + 0.25)^{\frac{1}{2}} }

In the last parenthesis, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x~} is equal to 1, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |y| = 0.25~} is lower than 1. Here is how we proceeded. Compute the perfect square lower than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2 + 3)~} , here it is 4. Change the sum within the parenthesis in order to display the perfect square. Get it outside the parenthesis, while applying the square root operation on both terms. Extract the square root from both, one requiring to use the binomial coefficients.

To compute the root square of the parenthesis, we use the row Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\frac{1}{2}}~} in the triangle.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1 + 0.25)^{\frac{1}{2}} = 1 + \frac{1}{2} \times 0.25 - \frac{1}{8} \times 0.25^2+ \cdots }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1 + 0.25)^{\frac{1}{2}} \approx 1 + \frac{1}{2} \times 0.25 - \frac{1}{8} \times 0.25^2=1.1171875 }

Using three terms, the square root estimate of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2 + 3)~} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 * 1.1171875 = 2.234375} . The square of this value is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4.9924316\dots} . Compared to the exact value, the error of calculating square root is close to 0.1%. Using more terms will sharpen the result.

We can compute any root with this method. However, it is not used in practice, since there are faster convergent methods, like the Newton-Raphson algorithm.

Computing the Logarithm of a Number

Starting with this equation :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+y)^2 = x^2 + 2 x y + y^2~} ,

we replace some terms within it :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+z)^2 = 1^2 + 2 \times 1 \times z + z^2~}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+z)^2 = 1 + 2 z + z^2~} ,

which is good for the square of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+z)~} . To compute the logarithm, we use the terms in row -1.

If we integrate both sides of the previous equation[8], we get the natural logarithm of a number[9] :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ln{(1+z)} = z - \frac{z^2}{2} + \frac{z^3}{3} - \frac{z^4}{4} + \frac{z^5}{5} - \frac{z^6}{6} + \frac{z^7}{7} +\cdots \text{ with } z \in \R \text{ and } -1 < z \leq 1 ~}

Matrix Exponential

At the beginning of the 21st century, someone found a remarkable equality between the Pascal's triangle and a power series of square matrices.[10]

As you probably know, we can compute the exponential function like this : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle e^x = \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \cdots } Moreover, maybe you remember that we can multiply a square matrix Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a_{{nn}}} of rank Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n} with any other square matrix of the same rank. Combining these two facts, we get

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e^{{a_{{nn}}}} = \frac{({{a_{{nn}}}})^0}{0!} + \frac{({{a_{{nn}}}})^1}{1!} + \frac{({{a_{{nn}}}})^2}{2!} + \cdots }

We are ready to compute the figurate number triangle of order 3 :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e^{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 1 & 0& 0 \\ 0 & 2& 0 \\ \end{array} \right]} = \frac{{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 1 & 0& 0 \\ 0 & 2& 0 \\ \end{array} \right]}^0}{0!} + \frac{{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 1 & 0& 0 \\ 0 & 2& 0 \\ \end{array} \right]}^1}{1!} + \frac{{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 1 & 0& 0 \\ 0 & 2& 0 \\ \end{array} \right]}^2}{2!} + \cdots }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e^{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 1 & 0& 0 \\ 0 & 2& 0 \\ \end{array} \right]} = \frac{{\left[ \begin{array}{ccc} 1 & 0& 0 \\ 0 & 1& 0 \\ 0 & 0& 1 \\ \end{array} \right]}}{1} + \frac{{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 1 & 0& 0 \\ 0 & 2& 0 \\ \end{array} \right]}}{1} + \frac{{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 0 & 0& 0 \\ 2 & 0& 0 \\ \end{array} \right]}}{2} + \cdots }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e^{\left[ \begin{array}{ccc} 0 & 0& 0 \\ 1 & 0& 0 \\ 0 & 2& 0 \\ \end{array} \right]} = \left[ \begin{array}{ccc} 1 & 0& 0 \\ 1 & 1& 0 \\ 1 & 2& 1 \\ \end{array} \right] }

To get bigger figurate number triangles, use bigger square matrices, filling the subdiagonal under the main diagonal with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 1, 2, 3, \cdots} , the rest is set to zero.

In combinatorics, the Pascal's triangle is simply defined by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \binom{n}{k} = \frac{n!}{k!(n-k)!}} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle k, n \in \N} . This compact equation provides the basis for many identities. However, it is not easy to manipulate through functions. The matrix exponential opens new territories, since it gives a new way to manipulate the triangle using results from the matrix theory and the function theory. For instance, is the triangle a solution of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle x^2 + 3x - 4I = 0 }  ? What is its inverse ? What is its logarithm ?

Normal Curve

Pascal's triangle lends itself to graphical representation. If you draw an histogram of the 19th row, you would get something like the following picture.

(GNU) Photo: Olier Raby
Histogram of the 19th row within the Pascal's triangle

Suppose we compute the terms of the 1000th row in Pascal's triangle. If we divide each term by 21000 and consider each value as a point on a continuous curve, we would get the following curve.

The normal curve, a limit case of any high-order row within the Pascal's Triangle.

Gauss, the famous German mathematician, studied the normal curve[11]. It is the commonest statistical law encountered in natural phenomenons[11][12]. For this reason, the properties of many statistical curves are compared to the normal curve properties. In its simplest form, its equation is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle P(z) = e^{-z^2/2}} .

Identities

We already presented some useful equations for building the Pascal's triangle. Since they are true within a field (a commutative ring), they are called identities in mathematics. Below, we list some more, but be aware there are literaly thousands of them.

1. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle x, y \in \R} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \in \N } ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k} }

with

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!} }

2. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \in \N} ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n \binom{n}{k} = 2^n }

3. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \in \N} ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} = 0 }

4. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \in \N} ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n 2^k \binom{n}{k} = 3^n }

5. (Pascal's identity) For ,

6. (Vandermonde's identity) For , , ,

7. For ,

8. For , ,

The previous identities remain true if the variables are complex (e.g., ). Some identities relating to Pascal's triangle are true when , , and are fractional.

9. ( Newton's identity) For and ,

with

When is an integer, we fall back on the first identity. The number of terms is still infinite, but almost all of them are equal to zero (those in the tail).

Unexpected Relations

Prime number multiples

Ones excepted, all the terms in any row where the second term is a prime number are multiple of the prime number. For instance, if a row starts with , then all its terms, ones excepted, are multiple of 23.[13]

Odd numbers within a row

Each row of order , only contains odd numbers. No other row has this property.

and

We saw the normal curve, a way to represent the binomial coefficients as a continuous curve. In its simplest form, its equation and the area under that curve is . The equation of this curve involves , while its area involves . How can this be possible, since the binomial coefficients are obtained by adding natural numbers, and we divided those coefficients by a power of 2 ?

Constructible polygons

Applying modulo 2 to every number in Pascal's triangle, we get

1

1 1

1 0 1

1 1 1 1

1 0 0 0 1

1 1 0 0 1 1

1 0 1 0 1 0 1

...

Viewing these ones and zeroes as binary digits, we get 1, 3, 5, 15, 17, 51,... in base ten. They are the number of sides found in constructible polygons with odd number of sides. This is true up to row 32.[14]

Computing

We can compute from the Pascal's triangle : . For instance, outputs . This formula is not used in practice since must be very large to compute to any decent precision.

Stacking marbles

If you stack marbles in the simplest 1D figure (along a line), then you arrange 1, 2, 3, 4,... marbles. If you stack marbles in the simplest 2D figure (triangle), then you arrange 1, 3, 6, 10,... marbles. If you stack marbles in the simplest 3D figure (a tetrahedron or 4-sided pyramid), then you arrange 1, 4, 10, 20,... marbles. If you stack marbles in the simplest 4D figure (a 4-simplex), then you arrange 1, 5, 15, 35,... marbles. And so on.

These numbers appear within the columns of the figurate number triangle, the column 1 contains the classic and basic counting numbers : 1, 2, 3, 4,... The column 2 contains the triangular numbers : 1, 3, 6, 10, 15, 21,... The column 3 contains the tetrahedral numbers : 1, 4, 10, 20, 35, 56,... The column 4 contains the pentatope numbers : 1, 5, 15, 35, 70, 126,... And so on.

Catalan numbers

The Pascal's triange hides the Catalan numbers.

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

...

Dividing the underlined numbers by 1, 2, 3, 4,..., we get 1, 1, 2, 5, 14,... The Catalan numbers appear in solutions of many combinatorial problems.[15] There is another way to compute these numbers : in the triangle, subtract the neighbour from each underlined number.

There is a surprising way to compute them. Square the terms in each row and add them :

These are the underlined values in the previous triangle.

Geometric counting

Somebody found a strange property relating geometry to the numbers within the Pascal's triangle.

A dot has one vertex (1). A segment has two vertices and one line (2,1). A triangle has three vertices, three edges and one surface (3, 3, 1). A triangular pyramid has four vertices, six edges, four surfaces and one volume (4, 6, 4, 1). And so on. Thus, the element count of a minimal regular geometric object (build from regular shapes) in 1D, 2D, 3D, 4D, etc., is specified by a row in the Pascal's triangle.

Bernoulli numbers

Bernoulli numbers, named in honor of Jacob Bernoulli who studied them intensively, arise in a wide variety of analytical and combinatorial contexts. They are[16]

Knowing that and are the two first terms of this series, we can compute all the terms :

, then

, then

, then

, then

, then

, then

is computed twice, but this arrangement clearly shows the binomial coefficients.[17]

References

  1. ↑ Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji, School of Mathematics and Statistics, University of St Andrews. Consulted 2005-09-03.
  2. ↑ 2.0 2.1 This rule does not apply to the ones bordering the triangle. We just insert them.
  3. ↑ Suppose we wish to add the terms in row 3, i.e. the fourth column, until row 6. The sum is given by multiplying four terms at numerator, starting at , and four terms at the denominator starting at . It is equal to . In short, fourth column, four terms at numerator, four terms at denominator, all decreasing.
  4. ↑ Equally, we can compute any triangle's term using , but it may exceed the calculator capacity !
  5. ↑ Eli Maor, e: The Story of a Number, Princeton University Press, 1994, p.71. ISBN 0-691-05854-7.
  6. ↑ Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, 1999, p. 636. ISBN 0-8493-9640-9
  7. ↑ The reason of this limitation is outside the scope of this article, it has to do with series convergence.
  8. ↑ From calculus, we know that :
  9. ↑ William H Beyer (ed.), Standard Mathematical Tables and Formulae, 29th edition, CRC Press, p.279. ISBN 0-8493-0629-9
  10. ↑ For instance, see Gottfried Helms, "Some Properties of the Binomial-("Pascal"-)-triangular matrix", 2005-08-31, version 3.
  11. ↑ 11.0 11.1 Template:Fr Jean-Louis Boursin, Les Structures du hasard, Seuil, coll. Les Rayons de la science, 1966, p.129.
  12. ↑ Paul Westbrook, Math Smart for Business: Cultivating a Six-Figure Vocabulary, Princeton Review, 1997, p. 70. ISBN 0679783911. Consulted 2007-11-19. View an extract at [1].
  13. ↑ See Pascal's Triangle From Top to Bottom, California State University, East Bay. Consulted 2007-11-28.
  14. ↑ Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, 1999, p. 1399. ISBN 0-8493-9640-9
  15. ↑ Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, 1999, p. 200. ISBN 0-8493-9640-9
  16. ↑ William H Beyer (ed.), Standard Mathematical Tables and Formulae, 29th edition, CRC Press, p.394. ISBN 0-8493-0629-9
  17. ↑ Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, 1999, p. 112. ISBN 0-8493-9640-9
Retrieved from "https://citizendium.org/wiki/index.php?title=Pascal%27s_triangle&oldid=984238"