Thebinomial coefficient appears as thekth entry in thenth row ofPascal's triangle (where the top is the 0th row). Each entry is the sum of the two above it.
The coefficient in each term is known as thebinomial coefficient or (the two have the same value). These coefficients for varying and can be arranged to formPascal's triangle. These numbers also occur incombinatorics, where gives the number of differentcombinations (i.e. subsets) ofelements that can be chosen from an-elementset. Therefore is usually pronounced as " choose".
According to the theorem, the expansion of any nonnegative integer powern of the binomialx +y is a sum of the formwhere each is a positive integer known as abinomial coefficient, defined as
This formula is also referred to as thebinomial formula or thebinomial identity. Usingsummation notation, it can be written more concisely as
The final expression follows from the previous one by the symmetry ofx andy in the first expression, and by comparison it follows that the sequence of binomial coefficients in the formula is symmetrical,
A simple variant of the binomial formula is obtained bysubstituting1 fory, so that it involves only a singlevariable. In this form, the formula reads
The first few cases of the binomial theorem are:In general, for the expansion of(x +y)n on the right side in thenth row (numbered so that the top row is the 0th row):
the exponents ofx in the terms aren,n − 1, ..., 2, 1, 0 (the last term implicitly containsx0 = 1);
the exponents ofy in the terms are0, 1, 2, ...,n − 1,n (the first term implicitly containsy0 = 1);
the coefficients form thenth row of Pascal's triangle;
before combining like terms, there are2n termsxiyj in the expansion (not shown);
after combining like terms, there aren + 1 terms, and their coefficients sum to2n.
An example illustrating the last two points: with.
A simple example with a specific positive value ofy:
A simple example with a specific negative value ofy:
Visualisation of binomial expansion up to the 4th power
For positive values ofa andb, the binomial theorem withn = 2 is the geometrically evident fact that a square of sidea +b can be cut into a square of sidea, a square of sideb, and two rectangles with sidesa andb. Withn = 3, the theorem states that a cube of sidea +b can be cut into a cube of sidea, a cube of sideb, threea ×a ×b rectangular boxes, and threea ×b ×b rectangular boxes.
Incalculus, this picture also gives a geometric proof of thederivative[1] if one sets and interpretingb as aninfinitesimal change ina, then this picture shows the infinitesimal change in the volume of ann-dimensionalhypercube, where the coefficient of the linear term (in) is the area of then faces, each of dimensionn − 1:Substituting this into thedefinition of the derivative via adifference quotient and taking limits means that the higher order terms, and higher, become negligible, and yields the formula interpreted as
"the infinitesimal rate of change in volume of ann-cube as side length varies is the area ofn of its(n − 1)-dimensional faces".
The coefficient ofxn−kyk is given by the formulawhich is defined in terms of thefactorial functionn!. Equivalently, this formula can be writtenwithk factors in both the numerator and denominator of thefraction. Although this formula involves a fraction, the binomial coefficient is actually aninteger.
The binomial coefficient can be interpreted as the number of ways to choosek elements from ann-element set (acombination). This is related to binomials for the following reason: if we write(x +y)n as aproductthen, according to thedistributive law, there will be one term in the expansion for each choice of eitherx ory from each of the binomials of the product. For example, there will only be one termxn, corresponding to choosingx from each binomial. However, there will be several terms of the formxn−2y2, one for each way of choosing exactly two binomials to contribute ay. Therefore, aftercombining like terms, the coefficient ofxn−2y2 will be equal to the number of ways to choose exactly2 elements from ann-element set.
Expanding(x +y)n yields the sum of the2n products of the forme1e2 ...en where eachei isx or y. Rearranging factors shows that each product equalsxn−kyk for somek between0 and n. For a givenk, the following are proved equal in succession:
the number of terms equal toxn−kyk in the expansion
the number ofn-characterx,y strings havingy in exactlyk positions
the number ofk-element subsets of{1, 2, ...,n}
either by definition, or by a short combinatorial argument if one is defining as
The coefficient ofxy2 inequals because there are threex,y strings of length 3 with exactly twoy's, namely,corresponding to the three 2-element subsets of{1, 2, 3}, namely,where each subset specifies the positions of they in a corresponding string.
Induction yields another proof of the binomial theorem. Whenn = 0, both sides equal1, sincex0 = 1 and Now suppose that the equality holds for a givenn; we will prove it forn + 1. Forj,k ≥ 0, let[f(x,y)]j,k denote the coefficient ofxjyk in the polynomialf(x,y). By the inductive hypothesis,(x +y)n is a polynomial inx andy such that[(x +y)n]j,k is ifj +k =n, and0 otherwise. The identityshows that(x +y)n+1 is also a polynomial inx andy, andsince ifj +k =n + 1, then(j − 1) +k =n andj + (k − 1) =n. Now, the right hand side isbyPascal's identity.[2] On the other hand, ifj +k ≠n + 1, then(j – 1) +k ≠n andj + (k – 1) ≠n, so we get0 + 0 = 0. Thuswhich is the inductive hypothesis withn + 1 substituted forn and so completes the inductive step.
Around 1665,Isaac Newton generalized the binomial theorem to allow real exponents other than nonnegative integers. (The same generalization also applies tocomplex exponents.) In this generalization, the finite sum is replaced by aninfinite series. In order to do this, one needs to give meaning to binomial coefficients with an arbitrary upper index, which cannot be done using the usual formula with factorials. However, for an arbitrary numberr, one can definewhere is thePochhammer symbol, here standing for afalling factorial. This agrees with the usual definitions whenr is a nonnegative integer. Then, ifx andy are real numbers with|x| > |y|,[Note 1] andr is any complex number, one has
Whenr is a nonnegative integer, the binomial coefficients fork >r are zero, so this equation reduces to the usual binomial theorem, and there are at mostr + 1 nonzero terms. For other values ofr, the series typically has infinitely many nonzero terms.
For example,r = 1/2 gives the following series for the square root:
Takingr = −1, the generalized binomial series gives thegeometric series formula, valid for|x| < 1:
More generally, withr = −s, we have for|x| < 1:[3]
So, for instance, whens = 1/2,
Replacingx with-x yields:
So, for instance, whens = 1/2, we have for|x| < 1:
The generalized binomial theorem can be extended to the case wherex andy are complex numbers. For this version, one should again assume|x| > |y|[Note 1] and define the powers ofx +y andx using aholomorphicbranch of log defined on an open disk of radius|x| centered atx. The generalized binomial theorem is valid also for elementsx andy of aBanach algebra as long asxy =yx, andx is invertible, and‖y/x‖ < 1.
A version of the binomial theorem is valid for the followingPochhammer symbol-like family of polynomials: for a given real constantc, define andfor Then[4]The casec = 0 recovers the usual binomial theorem.
More generally, a sequence of polynomials is said to beof binomial type if
for all,
, and
for all,, and.
An operator on the space of polynomials is said to be thebasis operator of the sequence if and for all. A sequence is binomial if and only if its basis operator is aDelta operator.[5] Writing for the shift by operator, the Delta operators corresponding to the above "Pochhammer" families of polynomials are the backward difference for, the ordinary derivative for, and the forward difference for.
The binomial theorem can be generalized to include powers of sums with more than two terms. The general version is
where the summation is taken over all sequences of nonnegative integer indicesk1 throughkm such that the sum of allki is n. (For each term in the expansion, the exponents must add up to n). The coefficients are known as multinomial coefficients, and can be computed by the formula
Combinatorially, the multinomial coefficient counts the number of different ways topartition ann-element set intodisjointsubsets of sizesk1, ...,km.
The general Leibniz rule gives thenth derivative of a product of two functions in a form similar to that of the binomial theorem:[6]
Here, the superscript(n) indicates thenth derivative of a function,. If one setsf(x) =eax andg(x) =ebx, cancelling the common factor ofe(a +b)x from each term gives the ordinary binomial theorem.[7]
Special cases of the binomial theorem were known since at least the 4th century BC whenGreek mathematicianEuclid mentioned the special case of the binomial theorem for exponent.[8] Greek mathematicianDiophantus cubed various binomials, including.[8] Indian mathematicianAryabhata's method for finding cube roots, from around 510 AD, suggests that he knew the binomial formula for exponent.[8]
Binomial coefficients, as combinatorial quantities expressing the number of ways of selectingk objects out ofn without replacement (combinations), were of interest to ancient Indian mathematicians. TheJainBhagavati Sutra (c. 300 BC) describes the number of combinations of philosophical categories, senses, or other things, with correct results up through (probably obtained by listing all possibilities and counting them)[9] and a suggestion that higher combinations could likewise be found.[10] TheChandaḥśāstra by the Indian lyricistPiṅgala (3rd or 2nd century BC) somewhat crypically describes a method of arranging two types of syllables to formmetres of various lengths and counting them; as interpreted and elaborated by Piṅgala's 10th-century commentatorHalāyudha his "method of pyramidal expansion" (meru-prastāra) for counting metres is equivalent toPascal's triangle.[11]Varāhamihira (6th century AD) describes another method for computing combination counts by adding numbers in columns.[12] By the 9th century at latest Indian mathematicians learned to express this as a product of fractions, and clear statements of this rule can be found inŚrīdhara'sPāṭīgaṇita (8th–9th century),Mahāvīra'sGaṇita-sāra-saṅgraha (c. 850), andBhāskara II'sLīlāvatī (12th century).[12][9][13]
The Persian mathematicianal-Karajī (953–1029) wrote a now-lost book containing the binomial theorem and a table of binomial coefficients, often credited as their first appearance.[14][15][16][17]An explicit statement of the binomial theorem appears inal-Samawʾal'sal-Bāhir (12th century), there credited to al-Karajī.[14][15] Al-Samawʾal algebraically expanded the square, cube, and fourth power of a binomial, each in terms of the previous power, and noted that similar proofs could be provided for higher powers, an early form ofmathematical induction. He then provided al-Karajī's table of binomial coefficients (Pascal's triangle turned on its side) up to and a rule for generating them equivalent to therecurrence relation.[15][18] The Persian poet and mathematicianOmar Khayyam was probably familiar with the formula to higher orders, although many of his mathematical works are lost.[8] The binomial expansions of small degrees were known in the 13th century mathematical works ofYang Hui[19] and alsoChu Shih-Chieh.[8] Yang Hui attributes the method to a much earlier 11th century text ofJia Xian, although those writings are now also lost.[20]
In Europe, descriptions of the construction of Pascal's triangle can be found as early asJordanus de Nemore'sDe arithmetica (13th century).[21] In 1544,Michael Stifel introduced the term "binomial coefficient" and showed how to use them to express in terms of, via "Pascal's triangle".[22] Other 16th century mathematicians includingNiccolò Fontana Tartaglia andSimon Stevin also knew of it.[22] 17th-century mathematicianBlaise Pascal studied the eponymous triangle comprehensively in hisTraité du triangle arithmétique.[23]
By the early 17th century, some specific cases of the generalized binomial theorem, such as for, can be found in the work ofHenry Briggs'Arithmetica Logarithmica (1624).[24]Isaac Newton is generally credited with discovering the generalized binomial theorem, valid for any real exponent, in 1665, inspired by the work ofJohn Wallis'sArithmetic Infinitorum and his method of interpolation.[22][25][8][26][24] A logarithmic version of the theorem for fractional exponents was discovered independently byJames Gregory who wrote down his formula in 1670.[24]
Using the binomial theorem, the expression on the right can be expanded, and then the real and imaginary parts can be taken to yield formulas forcos(nx) andsin(nx). For example, sinceBut De Moivre's formula identifies the left side with, sowhich are the usual double-angle identities. Similarly, sinceDe Moivre's formula yieldsIn general,andThere are also similar formulas usingChebyshev polynomials.
Applying the binomial theorem to this expression yields the usualinfinite series fore. In particular:
Thekth term of this sum is
Asn → ∞, the rational expression on the right approaches1, and therefore
This indicates thate can be written as a series:
Indeed, since each term of the binomial expansion is anincreasing function ofn, it follows from themonotone convergence theorem for series that the sum of this infinite series is equal to e.
The binomial theorem is closely related to the probability mass function of thenegative binomial distribution. The probability of a (countable) collection of independent Bernoulli trials with probability of success all not happening is
The binomial theorem is valid more generally for two elementsx andy in aring, or even asemiring, provided thatxy =yx. For example, it holds for twon ×n matrices, provided that those matrices commute; this is useful in computing powers of a matrix.[28]
^abBarth, Nils R. (2004). "Computing Cavalieri's Quadrature Formula by a Symmetry of then-Cube".The American Mathematical Monthly.111 (9):811–813.doi:10.2307/4145193.JSTOR4145193.
^Datta, Bibhutibhushan (1929)."The Jaina School of Mathematics".Bulletin of the Calcutta Mathematical Society.27. 5. 115–145 (esp. 133–134). Reprinted as "The Mathematical Achievements of the Jainas" inChattopadhyaya, Debiprasad, ed. (1982).Studies in the History of Science in India. Vol. 2. New Delhi: Editorial Enterprises. pp. 684–716.
^abGupta, Radha Charan (1992). "Varāhamihira's Calculation of and the Discovery of Pascal's Triangle".Gaṇita Bhāratī.14 (1–4):45–49. Reprinted inRamasubramanian, K., ed. (2019).Gaṇitānanda. Springer. pp. 285–289.doi:10.1007/978-981-13-1229-8_29.
^abcRashed, Roshdi (1972). "L'induction mathématique: al-Karajī, al-Samawʾal".Archive for History of Exact Sciences (in French).9 (1):1–21.doi:10.1007/BF00348537.JSTOR41133347. Translated into English by A. F. W. Armstrong inRashed, Roshdi (1994)."Mathematical Induction: al-Karajī and al-Samawʾal".The Development of Arabic Mathematics: Between Arithmetic and Algebra. Kluwer. §1.4, pp. 62–81.doi:10.1007/978-94-017-3274-1_2.ISBN0-7923-2565-6.The first formulation of the binomial and the table of binomial coefficients, to our knowledge, is to be found in a text by al-Karajī, cited by al-Samawʾal inal-Bāhir.
^Sesiano, Jacques (1997). "Al-Karajī". InSelin, Helaine (ed.).Encyclopaedia of the History of Science, Technology, and Medicine in Non-Western Cultures. Springer. pp. 475–476.doi:10.1007/978-94-017-1416-7_11.ISBN978-94-017-1418-1.Another [lost work of Karajī's] contained the first known explanation of the arithmetical (Pascal's) triangle; the passage in question survived through al-Samawʾal'sBāhir (twelfth century) which heavily drew from theBadīʿ.
^Berggren, John Lennart (1985). "History of mathematics in the Islamic world: The present state of the art".Review of Middle East Studies.19 (1):9–33.doi:10.1017/S0026318400014796. Republished inSidoli, Nathan;Brummelen, Glen Van, eds. (2014).From Alexandria, Through Baghdad. Springer. pp. 51–71.doi:10.1007/978-3-642-36736-6_4.ISBN978-3-642-36735-9.[...] since the table of binomial coefficients had been previously found in such late works as those of al-Kāshī (fifteenth century) and Naṣīr al-Dīn al-Ṭūsī (thirteenth century), some had suggested that the table was a Chinese import. However, the use of the binomial coefficients by Islamic mathematicians of the eleventh century, in a context which had deep roots in Islamic mathematics, suggests strongly that the table was a local discovery – most probably of al-Karajī.
^Martzloff, Jean-Claude (1997) [French ed. 1987]."Jia Xian and Liu Yi".A History of Chinese Mathematics. Translated by Wilson, Stephen S. Springer. p. 142.ISBN3-540-54749-5.
^Hughes, Barnabas (1989). "The arithmetical triangle of Jordanus de Nemore".Historia Mathematica.16 (3):213–223.doi:10.1016/0315-0860(89)90018-9.
^abcKline, Morris (1972).History of mathematical thought. Oxford University Press. p. 273.
^Katz, Victor (2009) [1993]. "Elementary Probability".A History of Mathematics: An Introduction (3rd ed.). Addison-Wesley. § 14.3, pp. 487–497.ISBN978-0-321-38700-4.
