Pascal's triangle

The Pascal's triangle is a convenient tabular presentation for the binomial coefficients. Already known in the 11th century, 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.

For instance, 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 (x+y)^4 = 1 \times a^4 + 4 \times a^3b + 6 \times a^2b^2 + 4 \times ab^3 + 1 \times b^4 ~}

The coefficients 1, 4, 6, 4, 1 appear directly 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 \begin{matrix} &&&&&1\\ &&&&1&&1\\ &&&1&&2&&1\\ &&1&&3&&3&&1\\ &1&&4&&6&&4&&1\\ &&&&&\cdots \end{matrix} }

Each coefficient in the triangle is the sum of the two coefficients over it. 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 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 (x+y)ⁿ, then

${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$

for any nonnegative integer n and any integer k between 0 and n.

Those coefficients have applications in algebra and in probabilities. From the triangle, we can equally compute the Fibonacci numbers 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.

Properties

In order to ease the understanding of some properties, the triangle should be presented differently :

${\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 the other to its left. For instance, $3+3=6$.

Let's call this rule the "addition rule".

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

${\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 $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 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 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 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. Again, we index the triangle, but this time it will be 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 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 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 .

Up until now, we added along the rows and the columns. We can add along the diagonals. Adding from left to right 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 & + & 1 & = & 21 \\ ...& & & & & & & & & = &... \\ \end{array} }

The numbers on the rigth are the Fibonacci numbers.

One row at a time

As you know by now, we can build any row if we know the row before just by adding its terms two at a time. It is possible to build a row directly, without knowing the row before. We will build the row 4 in order to discover the rule. We know that 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 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 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 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 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 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 \cdots ~}

Because it only applies to a row, we call it the "row rule". For any term, once the row and the column indices are know, we can compute is neighbour.

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^* ~}

Newton's Binomial Coefficients

Isaac Newton studied the triangle's properties. He discovered two remarkable generalizations.

He discovered that the triangle extends along the negative axis. To better understand how he achieve 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". To ease the understanding in the following text, we will call it the "Bernoulli triangle", even this matrix does not resemble a triangle anymore !

Using the row rule, lets 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} }

It is rather strange to see all those 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~} 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 -1~} . They seem outside the triangle. However, each term in this row obeys the addition rule and the row rule. Some quick 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 was fractional row indices, 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 \frac{1}{2}} .

And the answer is yes !

Let's use again the preceding example where we computed the terms of row 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 \begin{array}{lcccccc} 4: & 1 & 4 & 6 & 4 & 1 & \\ \end{array} }

<math>1 \times \frac{4 - 0}{1 + 0} = 4~<math>

<math>4 \times \frac{4 - 1}{1 + 1} = 6~<math>

<math>6 \times \frac{4 - 2}{1 + 2} = 4~<math>

<math> \cdots ~<math>

What is the first term of row <math>\frac{1}{2}<math>? By definition, it is 1. What are the terms after that ? We will use the row rule to copute them !

<math> 1 \times \frac{\frac{1}{2} - 0}{1 + 0} = \frac{1}{2} ~<math>

<math> \frac{1}{2} \times \frac{\frac{1}{2} - 1}{1 + 1} = -\frac{1}{8} ~<math>

<math> -\frac{1}{8} \times \frac{\frac{1}{2} - 2}{1 + 2} = \frac{1}{16} ~<math>

<math> \frac{1}{16} \times \frac{\frac{1}{2} - 3}{1 + 3} = -\frac{5}{128} ~<math>

<math> \cdots ~<math>

As you can see, no term goes to zero, even if it comes close.