Binomial theorem: Difference between revisions
Jump to navigation
Jump to search
imported>Zlamma →Newton's generalized binomial theorem: Fix style: remove repeated word use in one sentence: "...gives ... which gives..." |
imported>Chris the speller m punct |
||
| Line 1: | Line 1: | ||
{{short description|Algebraic expansion of powers of a binomial}} | {{short description|Algebraic expansion of powers of a binomial}} | ||
{{CS1 config|mode=cs1}} | {{CS1 config|mode=cs1}} | ||
{{Image frame|width= | {{Image frame|width=250 | ||
|content= | |content= | ||
<math> | <math> | ||
| Line 16: | Line 16: | ||
</math> | </math> | ||
|caption=The [[binomial coefficient]] <math>\tbinom{n}{k}</math> appears as the {{mvar|k}}th entry in the {{mvar|n}}th row of [[Pascal's triangle]] (where the top is the 0th row <math>\tbinom{0}{0}</math>). Each entry is the sum of the two above it.}} | |caption=The [[binomial coefficient]] <math>\tbinom{n}{k}</math> appears as the {{mvar|k}}th entry in the {{mvar|n}}th row of [[Pascal's triangle]] (where the top is the 0th row <math>\tbinom{0}{0}</math>). Each entry is the sum of the two above it.}} | ||
In [[elementary algebra]], the '''binomial theorem''' (or '''binomial expansion''') describes the [[Polynomial expansion|algebraic expansion]] of [[exponentiation|powers]] of a [[binomial (polynomial)|binomial]]. According to the theorem, the power {{tmath|\textstyle (x+y)^n}} expands into a [[polynomial]] with terms of the form {{tmath|\textstyle ax^ky^m }}, where the exponents {{tmath|k}} and {{tmath|m}} are [[nonnegative integer]]s satisfying {{tmath|1= k + m = n}} and the [[coefficient]] {{tmath|a}} of each term is a specific [[positive integer]] depending on {{tmath|n}} and {{tmath|k}}. | In [[elementary algebra]], the '''binomial theorem''' (or '''binomial expansion''') describes the [[Polynomial expansion|algebraic expansion]] of [[exponentiation|powers]] of a [[binomial (polynomial)|binomial]]. According to the theorem, the power {{tmath|\textstyle (x+y)^n}} expands into a [[polynomial]] with terms of the form {{tmath|\textstyle ax^ky^m }}, where the exponents {{tmath|k}} and {{tmath|m}} are [[nonnegative integer]]s satisfying {{tmath|1= k + m = n}} and the [[coefficient]] {{tmath|a}} of each term is a specific [[positive integer]] depending on {{tmath|n}} and {{tmath|k}}. For example, for {{tmath|1= n = 4}}, | ||
<math display=block>(x+y)^4 = x^4 + 4 x^3y + 6 x^2 y^2 + 4 x y^3 + y^4. </math> | <math display=block>(x+y)^4 = x^4 + 4 x^3y + 6 x^2 y^2 + 4 x y^3 + y^4. </math> | ||
The coefficient {{tmath|a}} in each term {{tmath|\textstyle ax^ky^m }} is known as the [[binomial coefficient]] {{tmath|\tbinom nk}} or {{tmath|\tbinom{n}{m} }} (the two have the same value). These coefficients for varying {{tmath|n}} and {{tmath|k}} can be arranged to form [[Pascal's triangle]]. These numbers also occur in [[combinatorics]], where {{tmath|\tbinom nk}} gives the number of different [[combinations]] (i.e. subsets) of {{tmath|k}} [[element (mathematics)|elements]] that can be chosen from an {{tmath|n}}-element [[set (mathematics)|set]]. | The coefficient {{tmath|a}} in each term {{tmath|\textstyle ax^ky^m }} is known as the [[binomial coefficient]] {{tmath|\tbinom nk}} or {{tmath|\tbinom{n}{m} }} (the two have the same value). These coefficients for varying {{tmath|n}} and {{tmath|k}} can be arranged to form [[Pascal's triangle]]<ref>{{Cite news |title=Pascal’s triangle {{!}} Definition & Facts {{!}} Britannica |url=https://www.britannica.com/science/Pascals-triangle |archive-url=http://web.archive.org/web/20250929213120/https://www.britannica.com/science/Pascals-triangle |archive-date=2025-09-29 |access-date=2026-03-25 |work=Encyclopedia Britannica |language=en}}</ref>. These numbers also occur in [[combinatorics]], where {{tmath|\tbinom nk}} gives the number of different [[combinations]] (i.e. subsets) of {{tmath|k}} [[element (mathematics)|elements]] that can be chosen from an {{tmath|n}}-element [[set (mathematics)|set]]. Therefore {{tmath|\tbinom nk}} is usually pronounced as "{{tmath|n}} choose {{tmath|k}}". | ||
== Statement == | == Statement == | ||
| Line 31: | Line 31: | ||
<math display="block">(x+y)^n = \sum_{k=0}^n {\binom{n}{k}}x^{n-k}y^k = \sum_{k=0}^n {\binom{n}{k}}x^{k}y^{n-k}.</math> | <math display="block">(x+y)^n = \sum_{k=0}^n {\binom{n}{k}}x^{n-k}y^k = \sum_{k=0}^n {\binom{n}{k}}x^{k}y^{n-k}.</math> | ||
The final expression follows from the previous one by the symmetry of {{mvar|x}} and {{mvar|y}} in the first expression, and by comparison it follows that the sequence of binomial coefficients in the formula is | The final expression follows from the previous one by the symmetry of {{mvar|x}} and {{mvar|y}} in the first expression, and by comparison it follows that the sequence of binomial coefficients in the formula is symmetric, <math display=inline>\binom nk = \binom n{n-k}.</math><ref group="Note"><math display="inline">(x+y)^n = \sum_{k=0}^n {\binom{n}{k}}x^{n-k}y^k = \sum_{k'=0}^n {\binom{n}{k'}}x^{k'}y^{n-k'}</math>, and the coefficient of the same [[monomial]] in the left and right-hand side expressions of the 2nd equality must be same; for <math display="inline">x^{n-k}y^k = x^{k'}y^{n-k'}</math> so <math display="inline">k' = n - k</math>, <math display="inline">\binom{n}{k} = \binom{n}{k'} = \binom{n}{n-k}</math>.</ref> | ||
A simple variant of the binomial formula is obtained by [[substitution (algebra)|substituting]] {{math|1}} for {{mvar|y}}, so that it involves only a single [[Variable (mathematics)|variable]]. In this form, the formula reads | A simple variant of the binomial formula is obtained by [[substitution (algebra)|substituting]] {{math|1}} for {{mvar|y}}, so that it involves only a single [[Variable (mathematics)|variable]]. In this form, the formula reads | ||
| Line 41: | Line 41: | ||
== Examples == | == Examples == | ||
[[File:Binomial expansion with Pascal's triangle.svg|thumb|Example of binomial expansion using Pascal's triangle]] | |||
The first few cases of the binomial theorem are: | The first few cases of the binomial theorem are: | ||
<math display="block">\begin{align} | <math display="block">\begin{align} | ||
(x+y)^0 & = 1, \\[ | (x+y)^0 & = 1, \\[2mu] | ||
(x+y)^1 & = x + y, \\[ | (x+y)^1 & = x + y, \\[2mu] | ||
(x+y)^2 & = x^2 + 2xy + y^2, \\[ | (x+y)^2 & = x^2 + 2xy + y^2, \\[2mu] | ||
(x+y)^3 & = x^3 + 3x^2y + 3xy^2 + y^3, \\[ | (x+y)^3 & = x^3 + 3x^2y + 3xy^2 + y^3, \\[2mu] | ||
(x+y)^4 & = x^4 | (x+y)^4 & = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4, | ||
\end{align}</math> | \end{align}</math> | ||
In general, for the expansion of {{math|(''x'' + ''y'')<sup>''n''</sup>}} on the right side in the {{mvar|n}}th row (numbered so that the top row is the 0th row): | In general, for the expansion of {{math|(''x'' + ''y'')<sup>''n''</sup>}} on the right side in the {{mvar|n}}th row (numbered so that the top row is the 0th row): | ||
| Line 79: | Line 81: | ||
In [[calculus]], this picture also gives a geometric proof of the [[derivative]] <math>(x^n)'=nx^{n-1}:</math><ref name="barth2004">{{cite journal | last = Barth | first = Nils R.| title = Computing Cavalieri's Quadrature Formula by a Symmetry of the ''n''-Cube | doi = 10.2307/4145193 | jstor = 4145193 | journal = The American Mathematical Monthly | volume = 111| issue = 9| pages = 811–813 | date=2004}}</ref> if one sets <math>a=x</math> and <math>b=\Delta x,</math> interpreting {{mvar|b}} as an [[infinitesimal]] change in {{mvar|a}}, then this picture shows the infinitesimal change in the volume of an {{mvar|n}}-dimensional [[hypercube]], <math>(x+\Delta x)^n,</math> where the coefficient of the linear term (in <math>\Delta x</math>) is <math>nx^{n-1},</math> the area of the {{mvar|n}} faces, each of dimension {{math|''n'' − 1}}: | In [[calculus]], this picture also gives a geometric proof of the [[derivative]] <math>(x^n)'=nx^{n-1}:</math><ref name="barth2004">{{cite journal | last = Barth | first = Nils R.| title = Computing Cavalieri's Quadrature Formula by a Symmetry of the ''n''-Cube | doi = 10.2307/4145193 | jstor = 4145193 | journal = The American Mathematical Monthly | volume = 111| issue = 9| pages = 811–813 | date=2004}}</ref> if one sets <math>a=x</math> and <math>b=\Delta x,</math> interpreting {{mvar|b}} as an [[infinitesimal]] change in {{mvar|a}}, then this picture shows the infinitesimal change in the volume of an {{mvar|n}}-dimensional [[hypercube]], <math>(x+\Delta x)^n,</math> where the coefficient of the linear term (in <math>\Delta x</math>) is <math>nx^{n-1},</math> the area of the {{mvar|n}} faces, each of dimension {{math|''n'' − 1}}: | ||
<math display="block">(x+\Delta x)^n = x^n + nx^{n-1}\Delta x + \binom{n}{2}x^{n-2}(\Delta x)^2 + \cdots.</math> | <math display="block">(x+\Delta x)^n = x^n + nx^{n-1}\Delta x + \binom{n}{2}x^{n-2}(\Delta x)^2 + \cdots.</math> | ||
Substituting this into the [[definition of the derivative]] via a [[difference quotient]] and taking limits means that the higher order terms, <math>(\Delta x)^2</math> and higher, become negligible, and yields the formula <math>(x^n)'=nx^{n-1},</math> interpreted as | Substituting this into the [[definition of the derivative]] via a [[difference quotient]] and taking limits means that the higher order terms, <math>(\Delta x)^2</math> and higher, become negligible, and yields the formula <math>(x^n)'=nx^{n-1},</math> interpreted as "the infinitesimal rate of change in volume of an {{mvar|n}}-cube as side length varies is the area of {{mvar|n}} of its {{math|(''n'' − 1)}}-dimensional faces". If one integrates this picture, which corresponds to applying the [[fundamental theorem of calculus]], one obtains [[Cavalieri's quadrature formula]], the integral <math>\textstyle{\int x^{n-1}\,dx = \tfrac{1}{n} x^n}</math> – see [[Cavalieri's quadrature formula#Proof|proof of Cavalieri's quadrature formula]] for details.<ref name="barth2004" /> | ||
If one integrates this picture, which corresponds to applying the [[fundamental theorem of calculus]], one obtains [[Cavalieri's quadrature formula]], the integral <math>\textstyle{\int x^{n-1}\,dx = \tfrac{1}{n} x^n}</math> – see [[Cavalieri's quadrature formula#Proof|proof of Cavalieri's quadrature formula]] for details.<ref name="barth2004" /> | |||
{{clear}} | {{clear}} | ||
| Line 125: | Line 125: | ||
=== Inductive proof === | === Inductive proof === | ||
[[mathematical induction|Induction]] yields another proof of the binomial theorem. When {{math|1=''n'' = 0}}, both sides equal {{math|1}}, since {{math|1=''x''<sup>0</sup> = 1}} and <math>\tbinom{0}{0}=1.</math> | [[mathematical induction|Induction]] yields another proof of the binomial theorem. When {{math|1=''n'' = 0}}, both sides equal {{math|1}}, since {{math|1=''x''<sup>0</sup> = 1}} and <math>\tbinom{0}{0}=1.</math> Now suppose that the equality holds for a given {{mvar|n}}; we will prove it for {{math|1=''n'' + 1}}. For {{math|1=''j'', ''k'' ≥ 0}}, let {{math|1=[''f''(''x'', ''y'')]<sub>''j'',''k''</sub>}} denote the coefficient of {{math|1=''x''<sup>''j''</sup>''y''<sup>''k''</sup>}} in the polynomial {{math|1=''f''(''x'', ''y'')}}. By the inductive hypothesis, {{math|1=(''x'' + ''y'')<sup>''n''</sup>}} is a polynomial in {{mvar|x}} and {{mvar|y}} such that {{math|1=[(''x'' + ''y'')<sup>''n''</sup>]<sub>''j'',''k''</sub>}} is <math>\tbinom{n}{k}</math> if {{math|1=''j'' + ''k'' = ''n''}}, and {{mvar|0}} otherwise. The identity | ||
<math display="block"> (x+y)^{n+1} = x(x+y)^n + y(x+y)^n</math> | <math display="block"> (x+y)^{n+1} = x(x+y)^n + y(x+y)^n</math> | ||
shows that {{math|1=(''x'' + ''y'')<sup>''n''+1</sup>}} is also a polynomial in {{mvar|x}} and {{mvar|y}}, and | shows that {{math|1=(''x'' + ''y'')<sup>''n''+1</sup>}} is also a polynomial in {{mvar|x}} and {{mvar|y}}, and | ||
| Line 137: | Line 137: | ||
== Generalizations == | == Generalizations == | ||
=== | === Generalized binomial theorem === | ||
{{Main|Binomial series}} | {{Main|Binomial series}} | ||
<math display="block">{\binom{r}{k}}=\frac{r(r-1) \cdots (r-k+1)}{k!} =\frac{ | The standard binomial theorem, as discussed above, is concerned with <math>(x+y)^n</math> where the exponent <math>n</math> is a nonnegative integer. The generalized binomial theorem allows for non-integer, negative, or even [[complex number|complex]] exponents, at the expense of replacing the finite sum by an [[infinite series]]. | ||
where | |||
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 number {{mvar|r}}, one can define | |||
<math display="block">{\binom{r}{k}}=\frac{r(r-1) \cdots (r-k+1)}{k!} =\frac{r^{\underline{k}}}{k!},</math><!--This is not the same as \frac{r!}{k!(r−k)!}. Please do not change it.--> | |||
where the last equation introduces modern notation for the [[falling factorial]]. This agrees with the usual definitions when {{mvar|r}} is a nonnegative integer. Then, if {{mvar|x}} and {{mvar|y}} are real numbers with {{math|{{abs|''x''}} > {{abs|''y''}}}},<ref name=convergence group=Note>This is to guarantee convergence. Depending on {{mvar|r}}, the series may also converge sometimes when {{math|1={{abs|''x''}} = {{abs|''y''}}}}.</ref> and {{mvar|r}} is any complex number, one has | |||
<math display="block">\begin{align} | <math display="block">\begin{align} | ||
(x+y)^r & =\sum_{k=0}^\infty {\binom{r}{k}} x^{r-k} y^k \\ | (x+y)^r & =\sum_{k=0}^\infty {\binom{r}{k}} x^{r-k} y^k \\ | ||
| Line 147: | Line 150: | ||
\end{align}</math> | \end{align}</math> | ||
When {{mvar|r}} is a nonnegative integer, the binomial coefficients for {{math|1=''k'' > ''r''}} are zero, so this equation reduces to the usual binomial theorem, and there are at most {{math|1=''r'' + 1}} nonzero terms. For other values of {{mvar|r}}, the series | When {{mvar|r}} is a nonnegative integer, the binomial coefficients for {{math|1=''k'' > ''r''}} are zero, so this equation reduces to the usual binomial theorem, and there are at most {{math|1=''r'' + 1}} nonzero terms. For other values of {{mvar|r}}, the series has infinitely many nonzero terms. | ||
For example, {{math|1=''r'' = 1/2}} gives the following series for the square root: | For example, {{math|1=''r'' = 1/2}} gives the following series for the square root: | ||
| Line 168: | Line 171: | ||
=== Further generalizations === | === Further generalizations === | ||
The generalized binomial theorem can be extended to the case where {{mvar|x}} and {{mvar|y}} are complex numbers. For this version, one should again assume {{math|{{abs|''x''}} > {{abs|''y''}}}}<ref name=convergence group=Note /> and define the powers of {{math|1=''x'' + ''y''}} and {{mvar|x}} using a [[Holomorphic function|holomorphic]] [[complex logarithm|branch of log]] defined on an open disk of radius {{math|{{abs|''x''}}}} centered at {{mvar|x}}. | The generalized binomial theorem can be extended to the case where {{mvar|x}} and {{mvar|y}} are complex numbers. For this version, one should again assume {{math|{{abs|''x''}} > {{abs|''y''}}}}<ref name=convergence group=Note /> and define the powers of {{math|1=''x'' + ''y''}} and {{mvar|x}} using a [[Holomorphic function|holomorphic]] [[complex logarithm|branch of log]] defined on an open disk of radius {{math|{{abs|''x''}}}} centered at {{mvar|x}}. The generalized binomial theorem is valid also for elements {{mvar|x}} and {{mvar|y}} of a [[Banach algebra]] as long as {{math|1=''xy'' = ''yx''}}, and {{mvar|x}} is invertible, and {{math|{{norm|''y''/''x''}} < 1}}. | ||
A version of the binomial theorem is valid for the following [[Pochhammer symbol]]-like family of polynomials: for a given real constant {{mvar|c}}, define <math> x^{(0)} = 1 </math> and | A version of the binomial theorem is valid for the following [[Pochhammer symbol]]-like family of polynomials: for a given real constant {{mvar|c}}, define <math> x^{(0)} = 1 </math> and | ||
<math display="block"> x^{(n)} = \prod_{k=1}^{n}[x+(k-1)c]</math> | <math display="block"> x^{(n)} = \prod_{k=1}^{n}[x+(k-1)c]</math> | ||
for <math> n > 0.</math> | for <math> n > 0.</math> Then<ref name="Sokolowsky">{{cite journal| url=https://cms.math.ca/publications/crux/issue/?volume=5&issue=2| title=Problem 352|first1=Dan|last1=Sokolowsky|first2=Basil C.|last2=Rennie|journal=Crux Mathematicorum|volume=5|issue=2|date=1979 | pages=55–56}}</ref> | ||
<math display="block"> (a + b)^{(n)} = \sum_{k=0}^{n}\binom{n}{k}a^{(n-k)}b^{(k)}.</math> | <math display="block"> (a + b)^{(n)} = \sum_{k=0}^{n}\binom{n}{k}a^{(n-k)}b^{(k)}.</math> | ||
The case {{math|1=''c'' = 0}} recovers the usual binomial theorem. | The case {{math|1=''c'' = 0}} recovers the usual binomial theorem. | ||
| Line 184: | Line 187: | ||
=== Multinomial theorem === | === Multinomial theorem === | ||
{{Main|Multinomial theorem}} | {{Main|Multinomial theorem}} | ||
The binomial theorem can be generalized to include powers of sums with more than two terms. The general version is | The binomial theorem can be generalized to include powers of sums with more than two terms. The general version is | ||
| Line 206: | Line 210: | ||
<math display="block">(fg)^{(n)}(x) = \sum_{k=0}^n \binom{n}{k} f^{(n-k)}(x) g^{(k)}(x).</math> | <math display="block">(fg)^{(n)}(x) = \sum_{k=0}^n \binom{n}{k} f^{(n-k)}(x) g^{(k)}(x).</math> | ||
Here, the superscript {{math|(''n'')}} indicates the {{mvar|n}}th derivative of a function, <math>f^{(n)}(x) = \tfrac{d^n}{dx^n}f(x)</math>. | Here, the superscript {{math|(''n'')}} indicates the {{mvar|n}}th derivative of a function, <math>f^{(n)}(x) = \tfrac{d^n}{dx^n}f(x)</math>. If one sets {{math|1=''f''(''x'') = ''e''{{sup|''ax''}}}} and {{math|1=''g''(''x'') = ''e''{{sup|''bx''}}}}, cancelling the common factor of {{math|''e''{{sup|(''a'' + ''b'')''x''}}}} from each term gives the ordinary binomial theorem.<ref>{{cite book |last1=Spivey |first1=Michael Z. |title=The Art of Proving Binomial Identities |date=2019 |publisher=CRC Press |isbn=978-1351215800 |page=71}}</ref> | ||
==History== | ==History== | ||
Special cases of the binomial theorem were known since at least the 4th century BC when [[Greek mathematics|Greek mathematician]] [[Euclid]] mentioned the special case of the binomial theorem for exponent <math>n=2</math>.<ref name="Coolidge">{{cite journal|title=The Story of the Binomial Theorem|first=J. L.|last=Coolidge|journal=The American Mathematical Monthly| volume=56| issue=3|date=1949|pages=147–157|doi=10.2307/2305028|jstor = 2305028}}</ref> Greek mathematician [[Diophantus]] cubed various binomials, including <math>x-1</math>.<ref name="Coolidge" /> | === Precursors === | ||
Special cases of the binomial theorem were known since at least the 4th century BC when [[Greek mathematics|Greek mathematician]] [[Euclid]] mentioned the special case of the binomial theorem for exponent <math>n=2</math>.<ref name="Coolidge">{{cite journal|title=The Story of the Binomial Theorem|first=J. L.|last=Coolidge|journal=The American Mathematical Monthly| volume=56| issue=3|date=1949|pages=147–157|doi=10.2307/2305028|jstor = 2305028}}</ref> Greek mathematician [[Diophantus]] cubed various binomials, including <math>x-1</math>.<ref name="Coolidge" /> Indian mathematician [[Aryabhata]]'s method for finding cube roots, from around 510 AD, suggests that he knew the binomial formula for exponent <math>n=3</math>.<ref name="Coolidge" /> | |||
Binomial coefficients, as combinatorial quantities expressing the number of ways of selecting {{mvar|k}} objects out of {{mvar|n}} without replacement ([[combinations]]), were of interest to ancient Indian mathematicians. The [[Jainism|Jain]] ''[[Bhagavati Sutra]]'' (c. 300 BC) describes the number of combinations of philosophical categories, senses, or other things, with correct results up through {{tmath|1= n = 4}} (probably obtained by listing all possibilities and counting them)<ref name=biggs>{{cite journal |last=Biggs |first=Norman L. |author-link=Norman L. Biggs |title=The roots of combinatorics |journal=Historia Mathematica |volume=6 |date=1979 |issue=2 |pages=109–136 |doi=10.1016/0315-0860(79)90074-0 |doi-access=free}}</ref> and a suggestion that higher combinations could likewise be found.<ref>{{cite journal |last=Datta |first=Bibhutibhushan |author-link=Bibhutibhushan Datta |url=https://archive.org/details/in.ernet.dli.2015.165748/page/n139/ |title=The Jaina School of Mathematics |journal=Bulletin of the Calcutta Mathematical Society |volume=27 |year=1929 |at=5. 115–145 (esp. 133–134) }} Reprinted as "The Mathematical Achievements of the Jainas" in {{cite book|editor-last=Chattopadhyaya |editor-first=Debiprasad |title=Studies in the History of Science in India |volume=2 |place=New Delhi |publisher=Editorial Enterprises |year=1982 |pages=684–716}}</ref> The ''[[Chandaḥśāstra]]'' by the Indian lyricist [[Piṅgala]] (3rd or 2nd century BC) somewhat cryptically describes a method of arranging two types of syllables to form [[metre (poetry)|metre]]s of various lengths and counting them; as interpreted and elaborated by Piṅgala's 10th-century commentator [[Halāyudha]] his "method of pyramidal expansion" (''meru-prastāra'') for counting metres is equivalent to [[Pascal's triangle]].<ref>{{cite journal |last=Bag |first=Amulya Kumar |title=Binomial theorem in ancient India |journal=Indian Journal of History of Science |volume=1 |number=1 |year=1966 |pages=68–74 |url=http://repository.ias.ac.in/70374/1/10-pub.pdf }} {{pb}} {{cite journal |last=Shah |first=Jayant |year=2013 |journal=Gaṇita Bhāratī |volume=35 |number=1–4 |pages=43–96 |title=A History of Piṅgala's Combinatorics |id={{ResearchGatePub|353496244}} }} ([https://ia800306.us.archive.org/19/items/Pingala/Pingala.pdf Preprint]) {{pb}} Survey sources: {{pb}} {{cite book |last=Edwards |first=A. W. F. |author-link=A. W. F. Edwards |year=1987 |chapter=The combinatorial numbers in India |title=Pascal's Arithmetical Triangle |place=London |publisher=Charles Griffin |isbn=0-19-520546-4 |chapter-url=https://archive.org/details/pascalsarithmeti0000edwa/page/27 |pages=27–33 |chapter-url-access=limited }} {{pb}} {{cite book |last=Divakaran |first=P. P. |year=2018 |title=The Mathematics of India: Concepts, Methods, Connections |chapter=Combinatorics |at=§5.5 {{pgs|135–140}} |publisher=Springer; Hindustan Book Agency |doi=10.1007/978-981-13-1774-3_5 |isbn=978-981-13-1773-6 }} {{pb}} {{cite book |last=Roy |first=Ranjan |author-link=Ranjan Roy |year=2021 |title=Series and Products in the Development of Mathematics |edition=2 |volume=1 |publisher=Cambridge University Press |chapter=The Binomial Theorem |at=Ch. 4, {{pgs|77–104}} |isbn=978-1-108-70945-3 |doi=10.1017/9781108709453.005 }}</ref> [[Varāhamihira]] (6th century AD) describes another method for computing combination counts by adding numbers in columns.<ref name=gupta>{{cite journal |last=Gupta |first=Radha Charan |author-link=Radha Charan Gupta |title=Varāhamihira's Calculation of {{tmath|{}^nC_r}} and the Discovery of Pascal's Triangle |journal=Gaṇita Bhāratī |volume=14 |number=1–4 |year=1992 |pages=45–49 }} Reprinted in {{cite book |editor-last=Ramasubramanian |editor-first=K. |year=2019 |title=Gaṇitānanda |publisher=Springer |doi=10.1007/978-981-13-1229-8_29 |pages=285–289 }}</ref> By the 9th century at latest Indian mathematicians learned to express this as a product of fractions {{tmath| \tfrac{n}1 \times \tfrac{n - 1}2 \times \cdots \times \tfrac{n - k + 1}{n-k} }}, and clear statements of this rule can be found in [[Śrīdhara]]'s ''Pāṭīgaṇita'' (8th–9th century), [[Mahāvīra (mathematician)|Mahāvīra]]'s ''[[Gaṇita-sāra-saṅgraha]]'' (c. 850), and [[Bhāskara II]]'s ''Līlāvatī'' (12th century).{{r|gupta}}{{r|biggs}}<ref>{{cite book |year=1959|title=The Patiganita of Sridharacarya |editor-last=Shukla |editor-first=Kripa Shankar |editor-link= Kripa Shankar Shukla |publisher=Lucknow University |chapter-url=https://archive.org/details/Patiganita/page/n294/mode/1up |chapter=Combinations of Savours |at=Vyavahāras 1.9, {{pgs|97}} (text), {{pgs|58–59}} (translation) }}</ref> | Binomial coefficients, as combinatorial quantities expressing the number of ways of selecting {{mvar|k}} objects out of {{mvar|n}} without replacement ([[combinations]]), were of interest to ancient Indian mathematicians. The [[Jainism|Jain]] ''[[Bhagavati Sutra]]'' (c. 300 BC) describes the number of combinations of philosophical categories, senses, or other things, with correct results up through {{tmath|1= n = 4}} (probably obtained by listing all possibilities and counting them)<ref name=biggs>{{cite journal |last=Biggs |first=Norman L. |author-link=Norman L. Biggs |title=The roots of combinatorics |journal=Historia Mathematica |volume=6 |date=1979 |issue=2 |pages=109–136 |doi=10.1016/0315-0860(79)90074-0 |doi-access=free}}</ref> and a suggestion that higher combinations could likewise be found.<ref>{{cite journal |last=Datta |first=Bibhutibhushan |author-link=Bibhutibhushan Datta |url=https://archive.org/details/in.ernet.dli.2015.165748/page/n139/ |title=The Jaina School of Mathematics |journal=Bulletin of the Calcutta Mathematical Society |volume=27 |year=1929 |at=5. 115–145 (esp. 133–134) }} Reprinted as "The Mathematical Achievements of the Jainas" in {{cite book|editor-last=Chattopadhyaya |editor-first=Debiprasad |title=Studies in the History of Science in India |volume=2 |place=New Delhi |publisher=Editorial Enterprises |year=1982 |pages=684–716}}</ref> The ''[[Chandaḥśāstra]]'' by the Indian lyricist [[Piṅgala]] (3rd or 2nd century BC) somewhat cryptically describes a method of arranging two types of syllables to form [[metre (poetry)|metre]]s of various lengths and counting them; as interpreted and elaborated by Piṅgala's 10th-century commentator [[Halāyudha]] his "method of pyramidal expansion" (''meru-prastāra'') for counting metres is equivalent to [[Pascal's triangle]].<ref>{{cite journal |last=Bag |first=Amulya Kumar |title=Binomial theorem in ancient India |journal=Indian Journal of History of Science |volume=1 |number=1 |year=1966 |pages=68–74 |url=http://repository.ias.ac.in/70374/1/10-pub.pdf }} {{pb}} {{cite journal |last=Shah |first=Jayant |year=2013 |journal=Gaṇita Bhāratī |volume=35 |number=1–4 |pages=43–96 |title=A History of Piṅgala's Combinatorics |id={{ResearchGatePub|353496244}} }} ([https://ia800306.us.archive.org/19/items/Pingala/Pingala.pdf Preprint]) {{pb}} Survey sources: {{pb}} {{cite book |last=Edwards |first=A. W. F. |author-link=A. W. F. Edwards |year=1987 |chapter=The combinatorial numbers in India |title=Pascal's Arithmetical Triangle |place=London |publisher=Charles Griffin |isbn=0-19-520546-4 |chapter-url=https://archive.org/details/pascalsarithmeti0000edwa/page/27 |pages=27–33 |chapter-url-access=limited }} {{pb}} {{cite book |last=Divakaran |first=P. P. |year=2018 |title=The Mathematics of India: Concepts, Methods, Connections |chapter=Combinatorics |at=§5.5 {{pgs|135–140}} |publisher=Springer; Hindustan Book Agency |doi=10.1007/978-981-13-1774-3_5 |isbn=978-981-13-1773-6 }} {{pb}} {{cite book |last=Roy |first=Ranjan |author-link=Ranjan Roy |year=2021 |title=Series and Products in the Development of Mathematics |edition=2 |volume=1 |publisher=Cambridge University Press |chapter=The Binomial Theorem |at=Ch. 4, {{pgs|77–104}} |isbn=978-1-108-70945-3 |doi=10.1017/9781108709453.005 }}</ref> [[Varāhamihira]] (6th century AD) describes another method for computing combination counts by adding numbers in columns.<ref name=gupta>{{cite journal |last=Gupta |first=Radha Charan |author-link=Radha Charan Gupta |title=Varāhamihira's Calculation of {{tmath|{}^nC_r}} and the Discovery of Pascal's Triangle |journal=Gaṇita Bhāratī |volume=14 |number=1–4 |year=1992 |pages=45–49 }} Reprinted in {{cite book |editor-last=Ramasubramanian |editor-first=K. |year=2019 |title=Gaṇitānanda |publisher=Springer |doi=10.1007/978-981-13-1229-8_29 |pages=285–289 }}</ref> By the 9th century at latest Indian mathematicians learned to express this as a product of fractions {{tmath| \tfrac{n}1 \times \tfrac{n - 1}2 \times \cdots \times \tfrac{n - k + 1}{n-k} }}, and clear statements of this rule can be found in [[Śrīdhara]]'s ''Pāṭīgaṇita'' (8th–9th century), [[Mahāvīra (mathematician)|Mahāvīra]]'s ''[[Gaṇita-sāra-saṅgraha]]'' (c. 850), and [[Bhāskara II]]'s ''Līlāvatī'' (12th century).{{r|gupta}}{{r|biggs}}<ref>{{cite book |year=1959|title=The Patiganita of Sridharacarya |editor-last=Shukla |editor-first=Kripa Shankar |editor-link= Kripa Shankar Shukla |publisher=Lucknow University |chapter-url=https://archive.org/details/Patiganita/page/n294/mode/1up |chapter=Combinations of Savours |at=Vyavahāras 1.9, {{pgs|97}} (text), {{pgs|58–59}} (translation) }}</ref> | ||
=== First appearance === | |||
[[File:Polynôme-Al-Samaw-al.jpg|thumb|Al-Samaw-al Polynomial. Illustration of the ''al-Bahir fi'l-Jabr'' "The Brilliant in Algebra" from the 12th century.]] | |||
The Persian mathematician [[al-Karajī]] (953–1029) wrote a now-lost book containing the binomial theorem and a table of binomial coefficients, often credited as their first appearance.<ref name=yadegari>{{cite journal |last=Yadegari |first=Mohammad |year=1980 |title=The Binomial Theorem: A Widespread Concept in Medieval Islamic Mathematics |journal=Historia Mathematica |volume=7 |issue=4 |pages=401–406 |doi=10.1016/0315-0860(80)90004-X |doi-access=free }}</ref><ref name=rashed>{{cite journal |last=Rashed |first=Roshdi |author-link=Roshdi Rashed |year=1972 |title=L'induction mathématique: al-Karajī, al-Samawʾal |journal=Archive for History of Exact Sciences |volume=9 |issue=1 |pages=1–21 |jstor=41133347 |doi=10.1007/BF00348537 |language=fr }} Translated into English by A. F. W. Armstrong in {{Cite book |last=Rashed |first=Roshdi |year=1994 |title=The Development of Arabic Mathematics: Between Arithmetic and Algebra |chapter=Mathematical Induction: al-Karajī and al-Samawʾal |chapter-url=https://archive.org/details/RoshdiRashedauth.TheDevelopmentOfArabicMathematicsBetweenArithmeticAndAlgebraSpringerNetherlands1994/page/n71/ |at=§1.4, {{pgs|62–81}} |doi=10.1007/978-94-017-3274-1_2 |publisher=Kluwer |isbn=0-7923-2565-6 |quote="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 in ''al-Bāhir''." }}</ref><ref>{{Cite encyclopedia |title=Al-Karajī |encyclopedia=Encyclopaedia of the History of Science, Technology, and Medicine in Non-Western Cultures |last=Sesiano |first=Jacques |editor-last=Selin |editor-first=Helaine |editor-link=Helaine Selin |year=1997 |publisher=Springer |doi=10.1007/978-94-017-1416-7_11 |isbn=978-94-017-1418-1 |pages=475–476 |quote=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's ''Bāhir'' (twelfth century) which heavily drew from the ''Badīʿ''. }}</ref><ref> | The Persian mathematician [[al-Karajī]] (953–1029) wrote a now-lost book containing the binomial theorem and a table of binomial coefficients, often credited as their first appearance.<ref name=yadegari>{{cite journal |last=Yadegari |first=Mohammad |year=1980 |title=The Binomial Theorem: A Widespread Concept in Medieval Islamic Mathematics |journal=Historia Mathematica |volume=7 |issue=4 |pages=401–406 |doi=10.1016/0315-0860(80)90004-X |doi-access=free }}</ref><ref name=rashed>{{cite journal |last=Rashed |first=Roshdi |author-link=Roshdi Rashed |year=1972 |title=L'induction mathématique: al-Karajī, al-Samawʾal |journal=Archive for History of Exact Sciences |volume=9 |issue=1 |pages=1–21 |jstor=41133347 |doi=10.1007/BF00348537 |language=fr }} Translated into English by A. F. W. Armstrong in {{Cite book |last=Rashed |first=Roshdi |year=1994 |title=The Development of Arabic Mathematics: Between Arithmetic and Algebra |chapter=Mathematical Induction: al-Karajī and al-Samawʾal |chapter-url=https://archive.org/details/RoshdiRashedauth.TheDevelopmentOfArabicMathematicsBetweenArithmeticAndAlgebraSpringerNetherlands1994/page/n71/ |at=§1.4, {{pgs|62–81}} |doi=10.1007/978-94-017-3274-1_2 |publisher=Kluwer |isbn=0-7923-2565-6 |quote="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 in ''al-Bāhir''." }}</ref><ref>{{Cite encyclopedia |title=Al-Karajī |encyclopedia=Encyclopaedia of the History of Science, Technology, and Medicine in Non-Western Cultures |last=Sesiano |first=Jacques |editor-last=Selin |editor-first=Helaine |editor-link=Helaine Selin |year=1997 |publisher=Springer |doi=10.1007/978-94-017-1416-7_11 |isbn=978-94-017-1418-1 |pages=475–476 |quote=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's ''Bāhir'' (twelfth century) which heavily drew from the ''Badīʿ''. }}</ref><ref> | ||
{{cite journal |last=Berggren |first=John Lennart |year=1985 |title=History of mathematics in the Islamic world: The present state of the art |journal=Review of Middle East Studies |volume=19 |number=1 |pages=9–33 |doi=10.1017/S0026318400014796 }} Republished in {{Cite book |title=From Alexandria, Through Baghdad |editor1-last=Sidoli |editor1-first=Nathan |editor2-last=Brummelen |editor2-first=Glen Van |editor2-link=Glen Van Brummelen |year=2014 |publisher=Springer |isbn=978-3-642-36735-9 |doi=10.1007/978-3-642-36736-6_4 |pages=51–71 |quote=[...] 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ī.}}</ref> | {{cite journal |last=Berggren |first=John Lennart |year=1985 |title=History of mathematics in the Islamic world: The present state of the art |journal=Review of Middle East Studies |volume=19 |number=1 |pages=9–33 |doi=10.1017/S0026318400014796 }} Republished in {{Cite book |title=From Alexandria, Through Baghdad |editor1-last=Sidoli |editor1-first=Nathan |editor2-last=Brummelen |editor2-first=Glen Van |editor2-link=Glen Van Brummelen |year=2014 |publisher=Springer |isbn=978-3-642-36735-9 |doi=10.1007/978-3-642-36736-6_4 |pages=51–71 |quote=[...] 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ī.}}</ref> | ||
An explicit statement of the binomial theorem appears in [[al-Samawʾal]]'s ''al-Bāhir'' (12th century), there credited to al-Karajī.{{r|yadegari}}{{r|rashed}} 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 of [[mathematical induction]]. He then provided al-Karajī's table of binomial coefficients (Pascal's triangle turned on its side) up to {{tmath|1= n = 12}} and a rule for generating them equivalent to the [[recurrence relation]] {{tmath|1=\textstyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} }}.{{r|rashed}}<ref name=Karaji>{{MacTutor|id=Al-Karaji|title=Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji}}</ref> The Persian poet and mathematician [[Omar Khayyam]] was probably familiar with the formula to higher orders, although many of his mathematical works are lost.<ref name="Coolidge" /> The binomial expansions of small degrees were known in the 13th century mathematical works of [[Yang Hui]]<ref>{{cite web | last = Landau | first = James A. | title = Historia Matematica Mailing List Archive: Re: [HM] Pascal's Triangle | work = Archives of Historia Matematica | format = mailing list email | access-date = 2007-04-13 | date = 1999-05-08 | url = http://archives.math.utk.edu/hypermail/historia/may99/0073.html | archive-date = 2021-02-24 | archive-url = https://web.archive.org/web/20210224081637/http://archives.math.utk.edu/hypermail/historia/may99/0073.html | url-status = dead }}</ref> and also [[Chu Shih-Chieh]].<ref name="Coolidge" /> | An explicit statement of the binomial theorem appears in [[al-Samawʾal]]'s ''al-Bāhir'' (12th century), there credited to al-Karajī.{{r|yadegari}}{{r|rashed}} 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 of [[mathematical induction]]. He then provided al-Karajī's table of binomial coefficients (Pascal's triangle turned on its side) up to {{tmath|1= n = 12}} and a rule for generating them equivalent to the [[recurrence relation]] {{tmath|1=\textstyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} }}.{{r|rashed}}<ref name=Karaji>{{MacTutor|id=Al-Karaji|title=Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji}}</ref> The Persian poet and mathematician [[Omar Khayyam]] was probably familiar with the formula to higher orders, although many of his mathematical works are lost.<ref name="Coolidge" /> The binomial expansions of small degrees were known in the 13th century mathematical works of [[Yang Hui]]<ref>{{cite web | last = Landau | first = James A. | title = Historia Matematica Mailing List Archive: Re: [HM] Pascal's Triangle | work = Archives of Historia Matematica | format = mailing list email | access-date = 2007-04-13 | date = 1999-05-08 | url = http://archives.math.utk.edu/hypermail/historia/may99/0073.html | archive-date = 2021-02-24 | archive-url = https://web.archive.org/web/20210224081637/http://archives.math.utk.edu/hypermail/historia/may99/0073.html | url-status = dead }}</ref> and also [[Chu Shih-Chieh]].<ref name="Coolidge" /> Yang Hui attributes the method to a much earlier 11th century text of [[Jia Xian]], although those writings are now also lost.<ref>{{cite book |title=A History of Chinese Mathematics |chapter=Jia Xian and Liu Yi |last=Martzloff |first=Jean-Claude |translator-last=Wilson |translator-first=Stephen S. |publisher=Springer |year=1997 |orig-year=French ed. 1987 |isbn=3-540-54749-5 |page=142 |chapter-url=https://archive.org/details/historyofchinese0000mart_g2q8/page/142/mode/2up?&q=%22depends+on+the+binomial+expansion%22 |chapter-url-access=limited }}</ref> | ||
In Europe, descriptions of the construction of Pascal's triangle can be found as early as [[Jordanus de Nemore]]'s ''De arithmetica'' (13th century).<ref>{{cite journal |last=Hughes |first=Barnabas|year=1989 |title=The arithmetical triangle of Jordanus de Nemore |journal=Historia Mathematica |volume=16 |number=3 |pages=213–223 |doi=10.1016/0315-0860(89)90018-9 |doi-access=free }}</ref> In 1544, [[Michael Stifel]] introduced the term "binomial coefficient" and showed how to use them to express <math>(1+x)^n</math> in terms of <math>(1+x)^{n-1}</math>, via "Pascal's triangle".<ref name=Kline>{{cite book| | In Europe, descriptions of the construction of Pascal's triangle can be found as early as [[Jordanus de Nemore]]'s ''De arithmetica'' (13th century).<ref>{{cite journal |last=Hughes |first=Barnabas|year=1989 |title=The arithmetical triangle of Jordanus de Nemore |journal=Historia Mathematica |volume=16 |number=3 |pages=213–223 |doi=10.1016/0315-0860(89)90018-9 |doi-access=free }}</ref> In 1544, [[Michael Stifel]] introduced the term "binomial coefficient" and showed how to use them to express <math>(1+x)^n</math> in terms of <math>(1+x)^{n-1}</math>, via "Pascal's triangle".<ref name="Kline">{{cite book |last=Kline |first=Morris |author-link=Morris Kline |url=https://archive.org/details/mathematicalthou0000unse/page/273 |title=Mathematical Thought From Ancient to Modern Times |publisher=Oxford University Press |year=1972 |page=273 |isbn=<!--not printed in the book 978-0-19-501496-9 --> |lccn=77-170263 }}</ref> Other 16th-century mathematicians, including [[Niccolò Fontana Tartaglia]] and [[Simon Stevin]], also knew of it.<ref name=Kline /> 17th-century mathematician [[Blaise Pascal]] studied the eponymous triangle comprehensively in his ''Traité du triangle arithmétique''.<ref>{{Cite book |last=Katz |first=Victor |author-link=Victor Katz |title=A History of Mathematics: An Introduction |edition=3rd |publisher=Addison-Wesley |year=2009 |orig-year=1993 |isbn=978-0-321-38700-4 |at=§ 14.3, {{pgs|487–497}} |chapter=Elementary Probability }}</ref> | ||
By the early 17th century, some specific cases of the generalized binomial theorem, such as for <math>n=\tfrac{1}{2}</math>, can be found in the work of [[Henry Briggs (mathematician)|Henry Briggs]]' ''Arithmetica Logarithmica'' (1624).{{r|stillwell}} [[Isaac Newton]] | === Generalized binomial theorem === | ||
The development of the binomial theorem for positive integer exponents in the form <math>(a+b)^n - a^n = C_{n,1}a^{n-1}b + C_{n,2}a^{n-2}b^2 + \cdots + C_{n,n-1}ab^{n-1} + b^n</math> is attributed to [[Persians|Persian]] mathematician [[Jamshid al-Kashi]] by the year 1427.<ref>{{Cite book |last=Simonyi |first=Károly |url=https://books.google.co.in/books?id=t9tFEQAAQBAJ&pg=PA138&dq=The+development+of+the+binomial+theorem+for+positive+integer+exponents+is+attributed+to+Jamshid+al-Kashi&hl=en&newbks=1&newbks_redir=0&source=gb_mobile_search&sa=X&ved=2ahUKEwiUnZPtwLCUAxWSSGwGHXOdHdIQ6AF6BAgIEAM#v=onepage&q=The%20development%20of%20the%20binomial%20theorem%20for%20positive%20integer%20exponents%20is%20attributed%20to%20Jamshid%20al-Kashi&f=false |title=A Cultural History of Physics |date=2025-02-28 |publisher=CRC Press |isbn=978-1-003-84930-8 |language=en}}</ref><ref>{{Cite book |last=Edwards |first=A. W. F. |url=https://books.google.co.in/books?id=CRmUDwAAQBAJ&pg=PA52&dq=binomial+theorem+al+Kashi+any+positive&hl=en&newbks=1&newbks_redir=0&source=gb_mobile_search&sa=X&ved=2ahUKEwjmvYfywbCUAxXV8zgGHc1WKyMQ6AF6BAgIEAM#v=onepage&q=binomial%20theorem%20al%20Kashi%20any%20positive&f=false |title=Pascal's Arithmetical Triangle |date=2019-06-12 |publisher=Courier Dover Publications |isbn=978-0-486-83279-1 |language=en}}</ref> Two foundational rules governing [[binomial coefficient]]s were documented in the work of [[Jamshīd al-Kāshī|al-Kashi]] around 1427. Historians suggest that earlier mathematicians of the [[Mathematics in medieval Islam|Islamic Golden Age]], including [[al-Tusi]], [[Omar Khayyam]], and [[Al-Karaji|al-Karji]], were likely already aware of these principles. | |||
Defining <math>C_{n,k}</math> as the coefficient of <math>x^k</math> in the algebraic expansion of <math>(1+x)^n</math>, these historical works by al-Kashi detail two primary formulas: | |||
* The additive rule, which allows the expansion of <math>(1+x)^n</math> to be derived from the expansion of <math>(1+x)^{n-1}</math>: | |||
:<math display="block">C_{n,k} = C_{n-1,k} + C_{n-1,k-1}</math> | |||
* The multiplicative rule, which yields the expansion directly: | |||
:<math display="block">C_{n,k} = \frac{n(n-1)\cdots(n-k+1)}{k!}</math> | |||
In European mathematics, [[Henry Briggs (mathematician)|Henry Briggs]] (1561–1630) is recognized as the first to explicitly record both formulas, although evidence suggests [[Gerolamo Cardano|Cardano]] may have independently known the results around 1570. The second formula was rigorously proven by [[Blaise Pascal|Pascal]] in 1654 through the use of [[complete induction]].<ref>{{Cite book |last=Roy |first=Ranjan |url=https://books.google.co.in/books?id=q8H3CwAAQBAJ&pg=PT75&dq=al+kashi+positive+exponent+binomial&hl=en&newbks=1&newbks_redir=0&source=gb_mobile_search&sa=X&ved=2ahUKEwj2i_vLu7CUAxW0xzgGHSZ3GYYQ6AF6BAgIEAM#v=onepage&q=al%20kashi%20positive%20exponent%20binomial&f=false |title=Sources in the Development of Mathematics: Series and Products from the Fifteenth to the Twenty-first Century |date=2011-06-13 |publisher=Cambridge University Press |isbn=978-1-139-49775-6 |language=en}}</ref> The first proper proof of the binomial theorem for positive integral index was given by Pascal.<ref>{{Cite book |last=Edwards |first=A. W. F. |author-link=A. W. F. Edwards |url=https://books.google.com/books?id=sx-EkudWKTcC&pg=PA55 |title=Pascal's Arithmetical Triangle: The Story of a Mathematical Idea |date=2002-07-23 |publisher=JHU Press |isbn=978-0-8018-6946-4 |pages=55, 79 |language=en}}</ref> By the early 17th century, some specific cases of the generalized binomial theorem, such as for <math>n=\tfrac{1}{2}</math>, can be found in the work of [[Henry Briggs (mathematician)|Henry Briggs]]' ''Arithmetica Logarithmica'' (1624).{{r|stillwell}} [[Isaac Newton]] discovered the generalized binomial theorem, valid for any real exponent, in 1664-5, inspired by the work of [[John Wallis]]'s ''Arithmetic Infinitorum'' and his method of interpolation.<ref name=Kline /><ref>{{Cite book |last=Edwards |first=C. Henry |url=https://archive.org/details/historicaldevelo0000edwa/page/167 |title=The Historical Development of the Calculus |date=1994 |publisher=Springer-Verlag |isbn=978-0-387-94313-8 |pages=167–169, 178–187 |doi=10.1007/978-1-4612-6230-5}}</ref><ref>{{Cite journal |last=Whiteside |first=D. T. |author-link=Tom Whiteside |date=1961 |title=Newton's Discovery of the General Binomial Theorem |url=https://www.cambridge.org/core/journals/mathematical-gazette/article/abs/newtons-discovery-of-the-general-binomial-theorem/19B5921B0248598CFB6441FCE085D113 |journal=The Mathematical Gazette |language=en |volume=45 |issue=353 |pages=175–180 |doi=10.2307/3612767 |jstor=3612767 |url-access=subscription }}</ref>{{r|stillwell}}<ref>{{Cite book |last1=Iliffe |first1=Rob |url=https://archive.org/details/the-cambridge-companion-to-newton/page/389 |title=The Cambridge Companion to Newton |last2=Smith |first2=George Edwin |date=2016 |publisher=Cambridge University Press |isbn=978-1-107-60174-1 |edition=2nd |location=Cambridge |pages=389–390|author-link2=George E. Smith (philosopher)}}</ref> A logarithmic version of the theorem for fractional exponents was discovered independently by [[James Gregory (mathematician)|James Gregory]] who wrote down his formula in 1670.<ref name=stillwell>{{cite book |last=Stillwell |first=John |author-link=John Stillwell |title=Mathematics and its history |date=2010 |publisher=Springer |isbn=978-1-4419-6052-8 |page=186 |edition=3rd}}</ref> | |||
== Applications == | == Applications == | ||
| Line 261: | Line 275: | ||
=== Probability === | === Probability === | ||
The binomial theorem is closely related to the probability mass function of the [[negative binomial distribution]]. The probability of a (countable) collection of independent Bernoulli trials <math>\{X_t\}_{t\in S}</math> with probability of success <math>p\in [0,1]</math> all not happening is | The binomial theorem is closely related to the probability mass function of the [[negative binomial distribution]]. The probability of a (countable) collection of independent Bernoulli trials <math>\{X_t\}_{t\in S}</math> with probability of success <math>p\in [0,1]</math> all not happening is | ||
<math display="block"> P\biggl(\bigcap_{t\in S} X_t^C\biggr) = (1-p)^{|S|} = \sum_{n=0}^{|S|} {\binom{|S|}{n}} (-p)^n.</math> | |||
An upper bound for this quantity is <math> e^{-p|S|}.</math><ref>{{Cite book |title=Elements of Information Theory |chapter=Data Compression |last1=Cover |first1=Thomas M. |author1-link=Thomas M. Cover |last2=Thomas |first2=Joy A. |author2-link=Joy A. Thomas |date=1991 |publisher=Wiley |isbn=9780471062592 |at=Ch. 5, {{pgs|78–124}} |doi=10.1002/0471200611.ch5}}<!-- a specific page number would be helpful. previously this citation noted p. 320 but that's not in this chapter. --> </ref> | An upper bound for this quantity is <math> e^{-p|S|}.</math><ref>{{Cite book |title=Elements of Information Theory |chapter=Data Compression |last1=Cover |first1=Thomas M. |author1-link=Thomas M. Cover |last2=Thomas |first2=Joy A. |author2-link=Joy A. Thomas |date=1991 |publisher=Wiley |isbn=9780471062592 |at=Ch. 5, {{pgs|78–124}} |doi=10.1002/0471200611.ch5}}<!-- a specific page number would be helpful. previously this citation noted p. 320 but that's not in this chapter. --> </ref> | ||
== In abstract algebra == | == In abstract algebra == | ||
The binomial theorem is valid more generally for two elements {{math|''x''}} and {{math|''y''}} in a [[Ring_(mathematics)|ring]], or even a [[semiring]], provided that {{math|1=''xy'' = ''yx''}}. | The binomial theorem is valid more generally for two elements {{math|''x''}} and {{math|''y''}} in a [[Ring_(mathematics)|ring]], or even a [[semiring]], provided that {{math|1=''xy'' = ''yx''}}. For example, it holds for two {{math|''n'' × ''n''}} matrices, provided that those matrices commute; this is useful in computing powers of a matrix.<ref>{{cite book |last=Artin |first=Michael |author-link=Michael Artin |title=Algebra |edition=2nd |year=2011 |publisher=Pearson |at=equation (4.7.11)}}</ref> | ||
The binomial theorem can be stated by saying that the [[polynomial sequence]] | The binomial theorem can be stated by saying that the [[polynomial sequence]] {{math|1={{mset|1, ''x'', ''x''<sup>2</sup>, ''x''<sup>3</sup>, ...}}}} is of [[binomial type]]. | ||
== See also == | == See also == | ||