Binomial theorem

From Wikipedia, the free encyclopedia

Pascal's triangle. Also called Tartaglia's triangle, and Yang Hui's Triangle, after others who invented the same triangle before Pascal.

In mathematics, the binomial theorem is an important formula giving the expansion of powers of sums. Its simplest version states that

$(x+y)^n=\sum_{k=0}^n{n \choose k}x^{n-k}y^{k}\quad\quad\quad(1)$

for any real or complex numbers x and y, and any non-negative integer n. The binomial coefficient appearing in (1) may be defined in terms of the factorial function n!:

${n \choose k}=\frac{n!}{k!\,(n-k)!}.$

For example, here are the cases where 2 ≤ n ≤ 5:

$(x + y)^2 = x^2 + 2xy + y^2\,$

$(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\,$

$(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4\,$

$(x + y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 +5xy^4 + y^5.\,$

Formula (1) is valid more generally for any elements x and y of a semiring as long as xy = yx. (The theorem is true even more generally: note that associativity is not required, just alternativity).

[edit] History

This formula and the triangular arrangement of the binomial coefficients are often attributed to Blaise Pascal, who described them in the 17th century, but they were known to many mathematicians who preceded him. The 4th century B.C. Greek mathematician Euclid knew a special case of the binomial theorem up to the second order,^[1]^[2] as did the 3rd century B.C. Indian mathematician Pingala to higher orders. A more general binomial theorem and the so-called "Pascal's triangle" were known to the 10th-century A.D. Indian mathematician Halayudha, the 11th-century A.D. Persian mathematician Omar Khayyám, and 13th-century Chinese mathematician Yang Hui, who all derived similar results.^[3]

[edit] Simple derivation

Consider $a = (x + y) n$ . a can be written as a product of sums, $a=s_1s_2 \cdots s_n$ , where each $s i = x + y$ . The expansion of a is the sum of all products involving one term—either x or y—from each $s i$ . For example, the term $x n$ in the expansion of a is had by picking x in each $s i$ .

The coefficient of each term in the expansion of a is determined by how many different ways there are to pick terms from the $s i$ such that their product is of the same form as the term (excluding the coefficient). Consider $t = x n - 1 y$ . t can be formed from a by picking y from one of the $s i$ and x in the rest of them. There are n ways to pick a $s i$ to provide the y; t is thus formed in n different ways in the expansion of a, making its coefficient n. In general, for $t = x n - k y k$ , there are

${n \choose k}$

different ways to pick the $s i$ that provide the ys (since k ys are picked from the n $s i$ ), and thus this must be the coefficient for t. The binomial theorem follows naturally from here.

[edit] Newton's generalized binomial theorem

Around 1665, Isaac Newton generalized the formula to allow exponents other than nonnegative integers. In this generalization, the finite sum is replaced by an infinite series. Namely, if x and y are real numbers with x > |y|,^[4] and r is any complex number, then

$\begin{align} (x+y)^r & =\sum_{k=0}^\infty {r \choose k} x^{r-k} y^k \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(2) \\ & = x^r + r x^{r-1} y + \frac{r(r-1)}{2!} x^{r-2} y^2 + \frac{r(r-1)(r-2)}{3!} x^{r-3} y^3 + \cdots. \end{align}$

When r is a nonnegative integer, the binomial coefficients for k > r are zero, so (2) specializes to (1), and there are at most r+1 nonzero terms. For other values of r, the series (2) has an infinite number of nonzero terms, at least if x and y are nonzero.

The coefficients can also be written

${r \choose k}=\frac{(r)_k}{k!},$

where $(\cdot)_k$ is the Pochhammer symbol. This is important when one is working with infinite series and would like to represent them in terms of generalized hypergeometric functions. This form is used in applied mathematics, for example, when evaluating the formulas that model the statistical properties of the phase-front curvature of a light wave as it propagates through optical atmospheric turbulence.^{[citation needed]}

Taking r = −s leads to a particularly handy but non-obvious formula:

$\frac{1}{(1-x)^s}=\sum_{k=0}^\infty {s+k-1 \choose k} x^k \equiv \sum_{k=0}^\infty {s+k-1 \choose s-1} x^k.$

Further specializing to s = 1 yields the geometric series formula.

[edit] Generalizations

Formula (2) can be generalized to the case where x and y are complex numbers. For this version, one should assume |x| > |y|^[4] and define the powers of x+y and x using a holomorphic branch of log defined on an open disk of radius |x| centered at x.

Formula (2) is valid also for elements x and y of a Banach algebra as long as xy = yx, x is invertible, and ||y/x|| < 1.

For a more extensive account of Newton's generalized binomial theorem, see binomial series.

[edit] "Binomial type"

The binomial theorem can be stated by saying that the polynomial sequence

$\left\{\,x^k:k=0,1,2,\dots\,\right\}\,$

is of binomial type.

[edit] Proof

One way to prove the binomial theorem (1) is with mathematical induction. When n = 0, we have

$(a+b)^0 = 1 = \sum_{k=0}^0 { 0 \choose k } a^{0-k}b^k.$

For the inductive step, assume the theorem holds when the exponent is m. Then for n = m + 1

$(a+b)^{m+1} = a(a+b)^m + b(a+b)^m \,$

$= a \sum_{k=0}^m { m \choose k } a^{m-k} b^k + b \sum_{j=0}^m { m \choose j } a^{m-j} b^j$

by the inductive hypothesis

$= \sum_{k=0}^m { m \choose k } a^{m-k+1} b^k + \sum_{j=0}^m { m \choose j } a^{m-j} b^{j+1}$

by multiplying through by a and b

$= a^{m+1} + \sum_{k=1}^m { m \choose k } a^{m-k+1} b^k + \sum_{j=0}^m { m \choose j } a^{m-j} b^{j+1}$

by pulling out the k = 0 term

$= a^{m+1} + \sum_{k=1}^m { m \choose k } a^{m-k+1} b^k + \sum_{k=1}^{m+1} { m \choose k-1 }a^{m-k+1}b^{k}$

by letting j = k − 1

$= a^{m+1} + \sum_{k=1}^m { m \choose k } a^{m-k+1}b^k + \sum_{k=1}^{m} { m \choose k-1 }a^{m+1-k}b^{k} + b^{m+1}$

by pulling out the k = m + 1 term from the right hand side

$= a^{m+1} + b^{m+1} + \sum_{k=1}^m \left[ { m \choose k } + { m \choose k-1 } \right] a^{m+1-k}b^k$

by combining the sums

$= a^{m+1} + b^{m+1} + \sum_{k=1}^m { m+1 \choose k } a^{m+1-k}b^k$

from Pascal's rule

$= \sum_{k=0}^{m+1} { m+1 \choose k } a^{m+1-k}b^k$

by adding in the 0 and m + 1 terms.

[edit] Binomial number

A binomial number is a number in the form of $\scriptstyle x^n \,\pm\, y^n$ (for n at least 2). When the sign is minus or n is odd these binomial numbers can be factored algebraically:

$x^n\pm y^n=(x\pm y)(x^{n-1} \mp x^{n-2}y + \cdots \mp xy^{n-2} + y^{n-1}).\,$

Examples:

$x^2-y^2=(x-y)(x+y)\,$

$x^3-y^3=(x-y)(x^2+xy+y^2)\,$

$x^3+y^3=(x+y)(x^2-xy+y^2)\,$

$x^8-y^8=(x-y)(x+y)(x^2+y^2)(x^4+y^4)\,$

To factor $\scriptstyle x^n\,-\,y^n$ simply, use

$x^n-y^n=(x-y) \left( \sum_{k=0}^{n-1}x^ky^{n-1-k} \right).$

[edit] A quick way to expand binomials

To quickly expand binomials of the form

$(x+y)^n \,$

The first term is

$x^n \,$

(this follows directly from the generalized binomial theorem) and the coefficient of each subsequent term is the current coefficient multiplied by the current exponent of x, divided by the current term number. Exponents of x decrease each term, while exponents of y increase each term (from 0 in the first term) until the exponent of x is 0 and that of y is n.

Example:

$(x+y)^{10} \,$

The first term is

$x^{10} \,$

To find the coefficient of the second term, multiply 1 (the current coefficient) by 10 (the current exponent of x), and divide by the current term number (1, since this is the first term) to get 10. The exponent of x decrements, and the exponent of y increments. The next term is therefore

$10x^9y \,$

Similarly, the next coefficient is (10×9)/(2×1), which gives 45. After that, it is (10×9×8)/(3×2×1). This continues until (10×9×8×7×6)/(5×4×3×2×1), after which, the coefficients are symmetrical. The whole thing is

x 10 + 10 x 9 y + 45 x 8 y 2 + 120 x 7 y 3 + 210 x 6 y 4 + 252 x 5 y 5 + 210 x 4 y 6 + 120 x 3 y 7 + 45 x 2 y 8 + 10 x y 9 + y 10 .

Notice that the coefficients are perfectly symmetrical. This will happen when the coefficients of x and y within the parentheses of the original expression are the same. Recognizing this can save even more time.

More formally, given a term

$kx^my^n \,$

The next term in the binomial is

$\frac{km}{n+1}x^{m-1}y^{n+1}=\frac{d}{dx}\left( \int kx^my^n\,dy\right)$

If the original expression instead was

$(2x+y)^{10} \,$

then the resulting expansion would be the same, except with (2x) in place of x in every place. The factor of 2 must get raised to the power of x in each term. The same holds true if either x or y is raised to a power inside the parentheses of the original expression.

[edit] The binomial theorem in popular culture

In the Sherlock Holmes books, the villain Professor Moriarty is the author of A Treatise on the Binomial Theorem.
The binomial theorem is mentioned in the Gilbert and Sullivan song "I am the Very Model of a Modern Major General".
The binomial theorem appears in at least three different works by Monty Python - Coal Mine in Llandarogh Carmarthen, The Tale of Happy Valley, and the film Monty Python's The Meaning of Life.
The binomial theorem is mentioned in the TV series NUMB3RS in episode #217 ("Mind Games") in Season 2.
Contrary to popular belief, the generalized binomial theorem is not engraved on Isaac Newton's tomb in Westminster Abbey.^[5]
In chapter 18 of Mikhail Bulgakov's "The Master and Margarita", the black magic practitioner Woland says, "But by Newton's binomial theorem, I predict that he will die in nine month's time..." From this, "it's hardly Newton's binomial theorem" became a popular Russian expression.
There is a short poem by Álvaro de Campos, heteronym of the Portuguese writer Fernando Pessoa about the binomial theorem that roughly translates into: "Newton's binomial is as beautiful as the Venus de Milo. The truth is few people notice it."
In record 5 of Yevgeny Zamyatin's We, the protagonist D-503 says, "...to me it's nothing more than the four equal angles, but for you that might be, I don't know, as tough as Newton's binomial theorem."

[edit] See also

The Wikibook Combinatorics has a page on the topic of

The Binomial Theorem

[edit] Notes

^ Binomial Theorem
^ The Story of the Binomial Theorem, by J. L. Coolidge, The American Mathematical MonthlyVol. 56, No. 3 (Mar., 1949), pp. 147-157
^ Landau, James A (1999-05-08). "Historia Matematica Mailing List Archive: Re: [HM] Pascal's Triangle" (mailing list email). Archives of Historia Matematica. http://archives.math.utk.edu/hypermail/historia/may99/0073.html. Retrieved on 2007-04-13.
^ ^a ^b This is to guarantee convergence. Depending on r, the series may also converge sometimes when |x| = |y|.
^ Cajori, Florian (1985). 'A History of Mathematics'. New York: Chelsea Publishing Company. pp. 205. ISBN 0-8284-1303-X.

[edit] References

Amulya Kumar Bag. Binomial Theorem in Ancient India. Indian J.History Sci.,1:68-74,1966.

[edit] External links

Binomial Theorem by Stephen Wolfram, and "Binomial Theorem (Step-by-Step)" by Bruce Colletti and Jeff Bryant, Wolfram Demonstrations Project, 2007.

This article incorporates material from inductive proof of binomial theorem on PlanetMath, which is licensed under the GFDL.

[0] Binomial Theorem

[1] The Story of the Binomial Theorem, by J. L. Coolidge, The American Mathematical MonthlyVol. 56, No. 3 (Mar., 1949), pp. 147-157

[2] Landau, James A (1999-05-08). "Historia Matematica Mailing List Archive: Re: [HM] Pascal's Triangle" (mailing list email). Archives of Historia Matematica. http://archives.math.utk.edu/hypermail/historia/may99/0073.html. Retrieved on 2007-04-13.

[convergence-3] This is to guarantee convergence. Depending on r, the series may also converge sometimes when |x| = |y|.

[4] Cajori, Florian (1985). 'A History of Mathematics'. New York: Chelsea Publishing Company. pp. 205. ISBN 0-8284-1303-X.

[1]

[2]

[3]

[4]

[5]

Binomial theorem

From Wikipedia, the free encyclopedia

Contents

[edit] History

[edit] Simple derivation

[edit] Newton's generalized binomial theorem

[edit] Generalizations

[edit] "Binomial type"

[edit] Proof

[edit] Binomial number

[edit] A quick way to expand binomials

[edit] The binomial theorem in popular culture

[edit] See also

[edit] Notes

[edit] References

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages