Difference between revisions of "Binomial Theorem"
I like pie (talk | contribs) m (→Generalization) |
m (Reverted edits by Marianasinta (talk) to last revision by Orange quail 9) (Tag: Rollback) |
||
(23 intermediate revisions by 13 users not shown) | |||
Line 2: | Line 2: | ||
<center><math>(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k</math></center> | <center><math>(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k</math></center> | ||
− | + | where <math>\binom{n}{k} = \frac{n!}{k!(n-k)!}</math> is a [[binomial coefficient]]. In other words, the coefficients when <math>(a + b)^n</math> is expanded and like terms are collected are the same as the entries in the <math>n</math>th row of [[Pascal's Triangle]]. | |
− | == | + | For example, <math>(a + b)^5 = a^5 + 5 a^4 b + 10 a^3 b^2 + 10 a^2 b^3 + 5 a b^4 + b^5</math>, with coefficients <math>1 = \binom{5}{0}</math>, <math>5 = \binom{5}{1}</math>, <math>10 = \binom{5}{2}</math>, etc. |
+ | |||
+ | ==Proof== | ||
+ | There are a number of different ways to prove the Binomial Theorem, for example by a straightforward application of [[mathematical induction]]. The Binomial Theorem also has a nice combinatorial proof: | ||
+ | |||
+ | We can write <math>(a+b)^n=\underbrace{ (a+b)\cdot(a+b)\cdot(a+b)\cdot\cdots\cdot(a+b) }_{n}</math>. Repeatedly using the [[distributive property]], we see that for a term <math>a^m b^{n-m}</math>, we must choose <math>m</math> of the <math>n</math> terms to contribute an <math>a</math> to the term, and then each of the other <math>n-m</math> terms of the product must contribute a <math>b</math>. Thus, the coefficient of <math>a^m b^{n-m}</math> is the number of ways to choose <math>m</math> objects from a set of size <math>n</math>, or <math>\binom{n}{m}</math>. Extending this to all possible values of <math>m</math> from <math>0</math> to <math>n</math>, we see that <math>(a+b)^n = \sum_{m=0}^{n}{\binom{n}{m}}\cdot a^m\cdot b^{n-m}</math>, as claimed. | ||
+ | |||
+ | Similarly, the coefficients of <math>(x+y)^n</math> will be the entries of the <math>n^\text{th}</math> row of [[Pascal's Triangle]]. This is explained further in the Counting and Probability textbook [AoPS]. | ||
+ | |||
+ | ===Proof via Induction=== | ||
+ | Given the constants <math>a,b,n</math> are all natural numbers, it's clear to see that <math>(a+b)^{1} = a+b</math>. Assuming that <math>(a+b)^{n} = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}</math>, <cmath>(a+b)^{n+1} = (\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k})(a+b)</cmath> | ||
+ | <cmath>=(\binom{n}{0}a^{n}b^{0} + \binom{n}{1}a^{n-1}b^{1} + \binom{n}{2}a^{n-2}b^{2}+\cdots+\binom{n}{n}a^{0}b^{n})(a+b)</cmath> | ||
+ | <cmath>=(\binom{n}{0}a^{n+1}b^{0} + \binom{n}{1}a^{n}b^{1} + \binom{n}{2}a^{n-1}b^{2}+\cdots+\binom{n}{n}a^{1}b^{n}) | ||
+ | + (\binom{n}{0}a^{n}b^{1} + \binom{n}{1}a^{n-1}b^{2} + \binom{n}{2}a^{n-2}b^{3}+\cdots+\binom{n}{n}a^{0}b^{n+1})</cmath> | ||
+ | <cmath>=(\binom{n}{0}a^{n+1}b^{0} + (\binom{n}{0}+\binom{n}{1})(a^{n}b^{1}) + (\binom{n}{1}+\binom{n}{2})(a^{n-1}b^{2})+\cdots+(\binom{n}{n-1}+\binom{n}{n})(a^{1}b^{n})+\binom{n}{n}a^{0}b^{n+1})</cmath> | ||
+ | <cmath>=\binom{n+1}{0}a^{n+1}b^{0} + \binom{n+1}{1}a^{n}b^{1} + \binom{n+1}{2}a^{n-1}b^{2}+\cdots+\binom{n+1}{n}a^{1}b^{n} + \binom{n+1}{n+1}a^{0}b^{n+1}</cmath> | ||
+ | <cmath>=\sum_{k=0}^{n+1}\binom{n+1}{k}a^{(n+1)-k}b^{k}</cmath> | ||
+ | Therefore, if the theorem holds under <math>n+1</math>, it must be valid. | ||
+ | (Note that <math>\binom{n}{m} + \binom{n}{m+1} = \binom{n+1}{m+1} </math> for <math>m\leq n</math>) | ||
+ | |||
+ | ===Proof using calculus=== | ||
+ | The [[Taylor series]] for <math>e^x</math> is <cmath>\sum_{n=0}^{\infty} \frac{x^n}{n!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \dots</cmath> for all <math>x</math>. | ||
+ | |||
+ | Since <math>e^{a+b} = e^ae^b</math>, and power series for the same function are termwise equal, the series at <math>x = a + b</math> is the [[Generating function#Convolutions|convolution]] of the series at <math>x = a</math> and <math>x = b</math>. Examining the degree-<math>n</math> term of each, <cmath>\frac{(a+b)^n}{n!} = \sum_{k=0}^{n} \left( \frac{a^k}{k!} \right) \left( \frac{b^{n-k}}{(n-k)!} \right),</cmath> which simplifies to <cmath>(a+b)^n = \sum_{k=0}^{n} \frac{n!}{k!(n-k)!}a^kb^{n-k}</cmath> for all [[Natural number|natural numbers]] <math>n</math>. | ||
+ | |||
+ | ==Generalizations== | ||
The Binomial Theorem was generalized by [[Isaac Newton]], who used an [[infinite]] [[series]] to allow for complex [[exponent]]s: For any [[real]] or [[complex]] <math>a</math>, <math>b</math>, and <math>r</math>, | The Binomial Theorem was generalized by [[Isaac Newton]], who used an [[infinite]] [[series]] to allow for complex [[exponent]]s: For any [[real]] or [[complex]] <math>a</math>, <math>b</math>, and <math>r</math>, | ||
− | <center><math>(a+b)^r = \sum_{k=0}^{\infty}\binom{r}{k}a^{r-k}b^k</math></center> | + | <center><math>(a+b)^r = \sum_{k=0}^{\infty}\binom{r}{k}a^{r-k}b^k</math>.</center> |
+ | |||
+ | ===Proof=== | ||
+ | Consider the function <math>f(b)=(a+b)^r</math> for constants <math>a,r</math>. It is easy to see that <math>\frac{d^k}{db^k}f=r(r-1)\cdots(r-k+1)(a+b)^{r-k}</math>. Then, we have <math>\frac{d^k}{db^k}f(0)=r(r-1)\cdots(r-k+1)a^{r-k}</math>. So, the [[Taylor series]] for <math>f(b)</math> centered at <math>0</math> is | ||
+ | |||
+ | <cmath>(a+b)^r=\sum_{k=0}^\infty \frac{r(r-1)\cdots(r-k+1)a^{r-k}b^k}{k!}=\sum_{k=0}^\infty \binom{r}{k}a^{r-k}b^k.</cmath> | ||
==Usage== | ==Usage== | ||
Line 16: | Line 46: | ||
[[Category:Theorems]] | [[Category:Theorems]] | ||
− | [[Category: | + | [[Category:Combinatorics]] |
+ | [[Category:Algebra]] |
Latest revision as of 12:11, 20 February 2024
The Binomial Theorem states that for real or complex , , and non-negative integer ,
where is a binomial coefficient. In other words, the coefficients when is expanded and like terms are collected are the same as the entries in the th row of Pascal's Triangle.
For example, , with coefficients , , , etc.
Contents
[hide]Proof
There are a number of different ways to prove the Binomial Theorem, for example by a straightforward application of mathematical induction. The Binomial Theorem also has a nice combinatorial proof:
We can write . Repeatedly using the distributive property, we see that for a term , we must choose of the terms to contribute an to the term, and then each of the other terms of the product must contribute a . Thus, the coefficient of is the number of ways to choose objects from a set of size , or . Extending this to all possible values of from to , we see that , as claimed.
Similarly, the coefficients of will be the entries of the row of Pascal's Triangle. This is explained further in the Counting and Probability textbook [AoPS].
Proof via Induction
Given the constants are all natural numbers, it's clear to see that . Assuming that , Therefore, if the theorem holds under , it must be valid. (Note that for )
Proof using calculus
The Taylor series for is for all .
Since , and power series for the same function are termwise equal, the series at is the convolution of the series at and . Examining the degree- term of each, which simplifies to for all natural numbers .
Generalizations
The Binomial Theorem was generalized by Isaac Newton, who used an infinite series to allow for complex exponents: For any real or complex , , and ,
Proof
Consider the function for constants . It is easy to see that . Then, we have . So, the Taylor series for centered at is
Usage
Many factorizations involve complicated polynomials with binomial coefficients. For example, if a contest problem involved the polynomial , one could factor it as such: . It is a good idea to be familiar with binomial expansions, including knowing the first few binomial coefficients.