Binomial Theorem

[Chand]

Any idea about Pascal's Triangle?

[Shadow]

Are you asking anything for anything specific or just want general information? If it's the latter case, wiki will probably give you a good start.

[Amaton]

Hi Chand

 

Basically, we have a binomial [math]x+y[/math], and raise it to a power. When we distribute all the binomials in the product, we end up with a sum of powers, each term having its own coefficient.

 

For example, [math](x+y)^2=(x+y)(x+y)=x^2+2xy+y^2[/math]. We see that the coefficients are: 1 2 1

 

Pascal's triangle simply organizes the coefficients for all the natural powers of [math]x+y[/math].

 

These are the first six rows of Pascal's Triangle (click for larger image)...

 

 

An interesting property of Pascal's triangle is that each number in it is a sum of the two numbers above it. Here's a visualization...

 

 

It's extremely useful when working in anything that involves binomial expansion. Since the coefficients in each row follow a pattern, you can pretty much expand any binomial straight from your head if you memorize just a few rows.

 

From here, the binomial theorem can be explained a little more easily. Questions so far?

Edited November 30, 2012 by Amaton

[Daedalus]

Another interesting fact is that the diagonal rows are increasing summations of [math]y=x[/math] or just [math]y=1[/math] if you consider the outside 1s: ) Furthermore, pascal's triangle shows up in many equations and algorithms ranging from simple algebra to finite calculus. This can be seen in the following formulas from my fourth challenge:

 

Newton's Interpolation:

 

Recursively take the deltas of each sequence:

 

[math] \begin{matrix} & & & y_4 - 3\, y_3 + 3\, y_2 - y_1\\ & & y_3 - 2\, y_2 + y_1 & y_4 - 2\, y_3 + y_2\\ & y_2 - y_1 & y_3 - y_2 & y_4 - y_3 \\ y_1 & y_2 & y_3 & y_4 \end{matrix} [/math]

 

We are only interested in the results at the top of each column. Also, we can see that each result is an alternating sum of the original sequence with coefficients that are pascal numbers. Next, we use each result with the rising factorial and standard factorial as follows:

 

[math]\left(y_1\right)\frac{1}{0!}\ -\ \left(y_2 - y_1\right)\frac{(1-x)}{1!}\ +\ \left(y_3 - 2\, y_2 + y_1\right)\frac{(1-x)(2-x)}{2!}\ -\ \left(y_4 - 3\, y_3 + 3\, y_2 - y_1\right)\frac{(1-x)(2-x)(3-x)}{3!}\ +\ \text{etc...}[/math]

 

The formula which defines this process is as defined below (note: I have expanded the formula to include recursively summing the sequence such that when [math]s=0[/math] we get the original sequence and when [math]s=1[/math] we get the first summation of the sequence and so on):

 

[math]F(x, \, s,\, n) = \sum_{i=0}^{n-1}\left( \sum_{j=0}^{i}\left(f(j)\frac{(-1)^{j}\ i!}{j!\ (i-j)!}\right) \frac{(-1)^{s}}{(i+s)!} \prod_{k=1}^{i+s}\left(k-s-x\right)\right)[/math]

 

Where [math]x[/math] is the variable, [math]s[/math] is the summation as explained above, and we sum from [math]0[/math] to [math]n-1[/math]. We can start from any number by modifying [math]f(j)[/math] to include a starting index, [math]f(j+start)[/math].

 

Daedalus' Exponential Interpolation:

 

We must do the same thing as above except we will divide the numbers of the sequence:

 

[math] \begin{matrix} & & & y_4^1 \times y_3^{-3} \times y_2^{3} \times y_1^{-1}\\ & & y_3^1 \times y_2^{-2} \times y_1^1 & y_4^1 \times y_3^{-2} \times y_2^1\\ & y_2^1 \times y_1^{-1} & y_3^1 \times y_2^{-1} & y_4^1 \times y_3^{-1} \\ y_1 & y_2 & y_3 & y_4 \end{matrix} [/math]

 

The next part is also similar except additions become multiplications, subtractions become division, and multiplication becomes exponents:

 

[math]\left(y_1\right)^{\frac{1}{0!}}\ \times\ \left(y_2^1 \times y_1^{-1}\right)^{-\frac{(1-x)}{1!}}\ \times \ \left(y_3^1 \times y_2^{-2} \times y_1^1\right)^{\frac{(1-x)(2-x)}{2!}}\ \times \ \left(y_4^1 \times y_3^{-3} \times y_2^{3} \times y_1^{-1}\right)^{-\frac{(1-x)(2-x)(3-x)}{3!}}\ \times \ \text{etc...}[/math]

 

The following formula defines the above process such that when [math]p=0[/math] we get the original sequence and when [math]p=1[/math] we get the first product of the sequence and so on:

 

[math]F(x, \, p,\, n) = \prod_{i=0}^{n-1}\left( \prod_{j=0}^{i}\left(f(j)^{\frac{(-1)^{j}\, i!}{j!\, (i-j)!}}\right)^{ \frac{(-1)^{p}}{(i+p)!} \displaystyle \prod_{k=1}^{i+p}\left(k-p-x\right)}\right)[/math]

 

Where [math]x[/math] is the variable, [math]p[/math] is the recursion level of the product as explained above, and we multiply the outputs from [math]0[/math] to [math]n-1[/math]. We can start from any number by modifying [math]f(j)[/math] to include a starting index, [math]f(j+start)[/math].

[ajb]

You can make a nice fractal from Pascal's triangle a which is related to the Sierpinski Sieve. There are many similar fractals that you can create, I created a mild generalisation for my blog.