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.

Here is the first rows of Pascal's triangle :

${\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

$(x+y)^{4}=1\times a^{4}+4\times a^{3}b+6\times a^{2}b^{2}+4\times ab^{3}+1\times b^{4}~$

The coefficients 1, 4, 6, 4, 1 appear directly in the triangle.

The terms in Pascal's triangle have applications in algebra and in probabilities. 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.

History

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 mathematices, most research most research was done within its descendants, like probabilities and combinatorics.

Formulas

Each coefficient in the triangle is the sum of the two coefficients above it. For instance, $6=3+3$. The binomial coefficients relate to this construction by Pascal's rule, which states that if

${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.

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 $r~$ being the row index : $0,1,2,\ldots ~$ For instance, the sum of row 4 is $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 :

${\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 $c~$ ending at row $r~$ is

${\frac {(r+1)\times r\,\times \cdots \times (r-c+1)}{(c+1)!}}{\text{ with }}r,c\in \mathbb {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 :

${\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 :

${\begin{array}{lcccccc}4:&1&4&6&4&1&\\\end{array}}$

$1\times {\frac {4-0}{1+0}}=4~$

$4\times {\frac {4-1}{1+1}}=6~$

$6\times {\frac {4-2}{1+2}}=4~$

$4\times {\frac {4-3}{1+3}}=1~$

$1\times {\frac {4-4}{1+4}}=0~$

$\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.

${\binom {r}{c+1}}={\binom {r}{c}}\times {\frac {r-c}{1+c}}{\text{ with }}r,c\in \mathbb {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 achieved this, let us write the triangle using another format :

${\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, let's compute the row -1 :

${\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 $1~$ and $-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.

${\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 ${\frac {1}{2}}$.

And the answer is yes !

Let's use again the preceding example where we computed the terms of row 4.

${\begin{array}{lcccccc}4:&1&4&6&4&1&\\\end{array}}$

$1\times {\frac {4-0}{1+0}}=4~$

$4\times {\frac {4-1}{1+1}}=6~$

$6\times {\frac {4-2}{1+2}}=4~$

$\cdots ~$

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

$1\times {\frac {{\frac {1}{2}}-0}{1+0}}={\frac {1}{2}}~$

${\frac {1}{2}}\times {\frac {{\frac {1}{2}}-1}{1+1}}=-{\frac {1}{8}}~$

$-{\frac {1}{8}}\times {\frac {{\frac {1}{2}}-2}{1+2}}={\frac {1}{16}}~$

${\frac {1}{16}}\times {\frac {{\frac {1}{2}}-3}{1+3}}=-{\frac {5}{128}}~$

$\cdots ~$

As you can see, no term goes to zero, even if each comes closer as it is further away from 1.

In the following augmented Bernoulli triangle, we added the row ${\frac {3}{2}}$ :

${\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}}$

A quick head calculation confirms that the rule works, as expected. After some trials, we conclude that the rule only works if the row indices have a difference of 1, 2, 3,...

Computing a Root Square

Newton's generalizations open new areas that were not primarily connected to the Pascal's triangle, namely with irrational numbers and logarithms. We are ready to compute the square root of a number.

We know this equation :

$(x+y)^{2}=x^{2}+2xy+y^{2}~$

If we replace $x~$ with 2 and $y~$ with 3, then we get

$(2+3)^{2}=2^{2}+2\times 2\times 3+3^{2}~$,

which is equal to 25, or $(2+3)^{2}=5^{2}~$. This is quite common knowledge, not to say it is boring.

Suppose we replace the exponent 2, an integer, by the exponent ${\frac {1}{2}}~$, a fraction. When it is 2, we get the square, when it is ${\frac {1}{2}}~$, we get the square root. This a rule of the exponentiation. Thus, we can use the triangle's coefficients to compute the square root.

This observation is technically correct, but there are some details that hugely simplify the calculations. If the exponent is a fraction, then $x~$ SHOULD be equal to 1 and, in this case, $y~$ MUST be equal to or less than 1. More preciseley, $|y|<1~$.

Let's compute $(2+3)^{\frac {1}{2}}~$, i.e. ${\sqrt {5}}~$.

$(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 parenthesis, $x~$ is equal to 1, and $|y|=0.25~$ is lower than 1. Here is how we proceeded. Compute the perfect square lower than $(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 carrying the square root operation on both terms. Extract the square root from both, one requiring to use the binomial coefficients.

Let's see how to compute the root square of the parenthesis.

We use the terms on the row ${\frac {1}{2}}~$.

$(1+0.25)^{\frac {1}{2}}=1+{\frac {1}{2}}\times 0.25-{\frac {1}{8}}\times 0.25+{\frac {1}{16}}\times 0.25-{\frac {5}{128}}\times 0.25+{\frac {7}{256}}\times 0.25-{\frac {21}{1024}}\times 0.25\cdots$

$(1+0.25)^{\frac {1}{2}}=1+0.25\times ({\frac {1}{2}}-{\frac {1}{8}}+{\frac {1}{16}}-{\frac {5}{128}}+{\frac {7}{256}}-{\frac {21}{1024}}\cdots )$

$(1+0.25)^{\frac {1}{2}}\approx 1.1013183593$

The estimate of the square root of $(2+3)~$ is $2*1.1013183593=2.202636718~$. The square of this value is $4.8516085~$. The error is around 3%, but we can sharpen the result by adding more terms.

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 :

$(x+y)^{2}=x^{2}+2xy+y^{2}~$,

and we replace some terms within it :

$(1+z)^{2}=1^{2}+2\times 1\times z+z^{2}~$

$(1+z)^{2}=1+2\times z+z^{2}~$

This is good for the square. To compute the logarithm, we use the terms in row -1.

$(1+z)^{-1}=1-z+z^{2}-z^{3}+z^{4}-z^{5}+z^{6}+\cdots ~$

From calculus, we know :

$\cdots ~$

$\int {z^{1}dz}={\frac {z^{2}}{2}}~$

$\int {z^{0}dz}={\frac {z^{1}}{1}}~$

$\int {z^{-1}dz}=\int {\frac {dz}{z}}=\ln {z}~$

$\int {z^{-2}dz}={\frac {z^{-1}}{-1}}~$

$\int {z^{-3}dz}={\frac {z^{-2}}{-2}}~$

$\cdots ~$

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

$\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 \mathbb {R} {\text{ and }}-1<z\leq 1~$