-2
$\begingroup$

So, I'm studying mathematics at a college level, and not very long ago I had a teacher tell us that the binomial theorem is as follows:

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

With virtually no form of proofing at all. Is there a way of proving this without doing basic crunch work and substituting in as many values as possible?

$\endgroup$
  • 2
    $\begingroup$ The standard way to write a sum is with \sum_{k=0}^n . $\endgroup$ – wythagoras Aug 23 '17 at 8:10
4
$\begingroup$

You can also prove it by induction:


For $n=0$, the equation becomes $$1=(a+b)^o = \sum_{k=0}^0 {0\choose k}a^{-k}b^k = 1\cdot a^0\cdot b^0=1$$

which is clearly correct.

Now, assume the equation is true for $n$, so we know $$(a+b)^n = \sum_{k=0}^n {n \choose k}a^{n-k}b^k.$$

Now,

$$\begin{align}(a+b)^{n+1} &= (a+b)(a+b)^n\\ &= (a+b)\sum_{k=0}^n {n \choose k}a^{n-k}b^k \\ &=a\sum_{k=0}^n {n \choose k}a^{n-k}b^k + b\sum_{k=0}^n {n \choose k}a^{n-k}b^k\\ &=\sum_{k=0}^n{n\choose k}a^{n-k+1}b^k + \sum_{k=0}^n {n \choose k}a^{n-k}b^{k+1} \end{align}$$

Now in the second sum, introduce $l=k+1$ to get

$$\begin{align}(a+b)^{n+1} &= \sum_{k=0}^n{n\choose k}a^{n-k+1}b^k + \sum_{l=1}^{n+1} {n \choose {l-1}}a^{n-l+1}b^{l}\\ &=\left({n\choose 0} a^{n+1}b^0 + \sum_{k=1}^n{n\choose k}a^{n-k+1}b^k\right) + \left(\sum_{l=1}^{n} {n \choose {l-1}}a^{n-l+1}b^{l}+{n \choose n}a^0b^{n+1}\right)\\ &=a^{n+1}b^0 + \sum_{k=1}^n\left({n\choose k} + {n\choose k-1}\right)a^{n+1-k}b^k + a^0b^{n+1}\end{align}$$

Now you just use the fact (that can easily be proven algebraically) that $${n\choose k} + {n\choose k-1} = {n+1\choose k}$$

and get

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

which concludes the proof.


For completeness:

$$\begin{align}{n\choose k}+{n\choose k-1} &= \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}\\ &=\frac{n!}{(k-1)!(n-k)!}\cdot\left(\frac{1}{k} + \frac{1}{n-k+1}\right)\\ &=\frac{n!}{(k-1)!(n-k)!}\cdot\frac{n-k+1 + k}{k(n-k+1)}\\ &=\frac{n!(n+1)}{(k-1)!\cdot k\cdot (n-k)!\cdot(n-k+1)}\\ &=\frac{(n+1)!}{k!((n+1)-k)!}\\ &={n+1\choose k}\end{align}$$

$\endgroup$
  • $\begingroup$ A very very good proof. I hadn't (until now) had time to investigate the rigorous proof, but this is very insightful. +1 $\endgroup$ – joshuaheckroodt Aug 23 '17 at 8:33
  • 3
    $\begingroup$ @joshuaheckroodt I advise you to always examine the rigorous proofs. Because when you get down to it, there are only two kinds of proofs: those that can be made rigorously, and those that are false. $\endgroup$ – 5xum Aug 23 '17 at 8:34
  • $\begingroup$ Sound advice. I'll be sure to take it whenever I next get the chance to do so. $\endgroup$ – joshuaheckroodt Aug 23 '17 at 8:36
5
$\begingroup$

Combinatorial Approach

First Let's consider when $n=4$. We wish to find the coefficient of $x^2y^2$ in the expansion of $(x+y)^4$. The coefficient of $x^2y^2$ is the number of different ways in which we can select two $x$'s and two $y$'s in the expansion of the product $(x+y)(x+y)(x+y)(x+y)$. For example, we can select two $x$'s from the first two factors and the two $y$'s from the last two factors. The following table shows different possible ways. $$ \begin{array}{c|c} \text{Factors for selecting two }x&\text{Factors for selecting two }y\\ \hline 1,2&3,4\\ 1,3&2,4\\ 1,4&2,3\\ 2,3&1,4\\ 2,4&1,3\\ 3,4&1,2 \end{array} $$ so there are $6$ different ways. Hence, the coefficient of $x^2y^2$ in the expansion of $(x+y)^4$ is $6$.

Now let's look at the general case $(x+y)^n$ where $n\in\mathbb{N}$ and $x$ and $y$ are any two variables. The coefficient of $x^ky^{n-k}$ (where $0\leq k\leq n$) is the number of different ways in which we can select $k$ $x$'s and $(n-k)$ $y$'s in the expansion of the product $$ \underbrace{(x+y)(x+y)\ldots(x+y)}_{n\text{ copies}} $$ One way for instance, is to select $k$ $x$'s from the first $k$ factors and $n-k$ $y$'s from the remaining $n-k$ factors. There are $\binom{n}{k}$ different ways of selecting $k$ $x$'s and $(n-k)$ $y$'s. Hence, the coefficient of $x^ky^{n-k}$ is $\binom{n}{k}$.

$\endgroup$
  • $\begingroup$ This is a very carefully thought out approach. Thank you :) $\endgroup$ – joshuaheckroodt Aug 23 '17 at 8:57
1
$\begingroup$

Short answer is yes. Seeing as this is the grand total of exposure you have to the binomial theorem, I'll stick to a non-rigorous proof, but lets do as you did and start with the crunch work;

$(a+b)^2=a^2+2ab+b^2$

$(a+b)^3=a^3+3a^2b+3ab^2+b^3$

$(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^3$

and look for patterns. The first thing you might notice is that the degree of $a$ decreases with every next term, and the degree of $b$ increases. So, in actual fact, starting with the first term ($k$), $0$, the degree of $a$ will always be $n-k$, where $n$ is the degree of the expansion and $k$ is obviously the position of the term, whereas $b$ will always have a degree of $k$, so, without coefficients:

$(a+b)^2=a^2+ab+b^2$

$(a+b)^3=a^3+a^2b+ab^2+b^3$

$(a+b)^2=a^4+a^3b+a^2b^2+ab^3+b^4$

$(a+b)^n=a^n+a^{n-1}b^1+a^{n-2}b^2+\ldots+a^{n-k}b^k$

And now for the coefficients. Noticing the pattern in the degree was easy enough, but the coefficients are a little harder, so lets look solely at the coefficients:

$(a+b)^2=1+2+1$

$(a+b)^3=1+3+3+1$

$(a+b)^4=1+4+6+4+1$

From here, you might notice that actually, the coefficients map Pascal's triangle:

enter image description here

And although this is useful, it seems illogical to simply memorise the whole Pascal's triangle. So, there are two alternatives, the one is to simply remember that any value on Pascal's triangle is a sum of the two values above it, or to remember the following variation of the triangle,

enter image description here

in which the rule of thumb is $\displaystyle {n \choose k}$, where $n$ is the row number, which also corresponds with the degree of the expansion, and $k$ is the position along the row, which also corresponds with the position of the term. Now, don't worry too much about the reliability of the triangle, as it was originally discovered as an array of known binomial coefficients by Blaise Pascal, and is hence therefore almost solely dedicated to identifying binomial coefficients.

So now we have the coefficients, $\displaystyle {n \choose k}$ and the variables with their degrees $\displaystyle a^{n-k}b^k$, and hence all that's left is to add all the terms together using the method of summation as follows:

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

which corresponds exactly to the given theorem.

$\endgroup$
  • 1
    $\begingroup$ You could prove it rigorously by induction on $n$. $\endgroup$ – Michael Hartley Aug 23 '17 at 8:12
  • 2
    $\begingroup$ Your final equation should read $$(a + b)^n = \sum_{k = 0}^{n} \binom{n}{k}a^{n - k}b^k$$ Also, Pascal rediscovered Pascal's Triangle. It had been discovered before in other cultures. Pascal is famous for proving relationships among the coefficients. $\endgroup$ – N. F. Taussig Aug 23 '17 at 8:36
0
$\begingroup$

I assume that you are given the definition

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

and want to see how the binomial theorem is proven from this definition.

Be aware that some sources define the binomial coefficients to be the coefficients appearing in the binomial formula, so the statement you ask to be proved is true by definition!


You can compute the Taylor series for $f(x) = x^n$ around $x=a$. The derivatives of this function are:

  • $f(x) = x^n$
  • $f'(x) = n x^{n-1}$
  • $f''(x) = n (n-1) x^{n-2}$
  • $\vdots$

It's not hard to see that

$$ f^{(k)}(x) = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) \cdot x^{n-k} $$

and consequently, the Taylor series about $x-a$ is

$$ x^n = \sum_{k=0}^{\infty} \frac{f^{(k)}(a)}{k!} (x-a)^k $$

and the sum can be seen to converge on $|x-a| < |a|$.

(aside: I am implicitly using the fact that $x^n$ is known to be an analytic function of $x$)

Plugging in $x = a+b$, we have

$$ (a+b)^n = \sum_{k=0}^{\infty} \frac{f^{(k)}(a)}{k!} b^k $$

(if $|b| > |a|$, we can reduce to the above case by rewriting $(a+b)^n = (b+a)^n$. The $|a| = |b|$ case can be handled separately)

If $n$ is a nonnegative integer, we can simplify

$$ f^{(k)}(x) = \begin{cases} \frac{n!}{(n-k)!} & k \leq n \\ 0 & k > n \end{cases} $$

and so the sum simplifies to

$$ (a+b)^n = \sum_{k=0}^{\infty} \frac{n!}{k!(n-k)!} a^{n-k} b^k $$


Incidentally, this formula also works when $n$ is an arbitrary complex number. If we define the (generalized) binomial coefficient to be

$$ \binom{n}{k} = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}{k!} $$

whenever $k$ is a nonnegative integer, then we still have the identity

$$ (a+b)^z = \sum_{k=0}^{\infty} \binom{z}{k} a^{n-k} b^k $$

$\endgroup$
0
$\begingroup$

The Binomial Theorem can be proved from Taylor's Series. I've been working on these proofs so I'll just include the Dropbox links for them. As far as real positive integers go :

[ Binomial Theorem ] :

https://www.dropbox.com/s/8o86y6cxsrkzztq/Binomial%20Theorem.pdf?dl=0

If you are unfamiliar with the Maclaurin Series (it is a special case of Taylor Series), I've also included documents that will hopefully help with that.

[ Taylor Series ] :

https://www.dropbox.com/s/pkl3krcwafgmsx2/Taylor%20Series.pdf?dl=0

[ Maclaurin Series ] :

https://www.dropbox.com/s/eqsux2ts95jor73/Maclaurin%20Series.pdf?dl=0

[ Derivative of $x^n$ from First Principles (ii) ] (Courtesy of Vafa Khalighi) :

https://www.dropbox.com/s/6n20hrnhpo1dlac/Derivative%20of%20x%5En%20from%20First%20Principles%20%28ii%29.pdf?dl=0

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.