Difference between revisions of "Binomial Theorem"
Wuwang2002 (talk | contribs) ($\LaTeX$ fix) |
(Added a proof using calculus (the Taylor series of e^x)) |
||
Line 23: | Line 23: | ||
Therefore, if the theorem holds under <math>n+1</math>, it must be valid. | 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>) | (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^ae^b = e^{a+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^nb^{n-k}</cmath> for all [[Natural number|natural numbers]] <math>n</math>. | ||
==Generalizations== | ==Generalizations== |
Revision as of 22:32, 9 March 2022
The Binomial Theorem states that for real or complex ,
, and non-negative integer
,
![$(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$](http://latex.artofproblemsolving.com/4/9/4/494769588adb2ac3700e25b086fe2b7d41bba70a.png)
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
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
,
![$(a+b)^r = \sum_{k=0}^{\infty}\binom{r}{k}a^{r-k}b^k$](http://latex.artofproblemsolving.com/0/8/9/0896503fb81e2e64fc5d22e03210b9fc46b7ce32.png)
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.