Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3.2: Newton's Binomial Theorem

( \newcommand{\kernel}{\mathrm{null}\,}\)

Recall that

(nk)=n!k!(nk)!=n(n1)(n2)(nk+1)k!.

The expression on the right makes sense even if n is not a non-negative integer, so long as k is a non-negative integer, and we therefore define

(rk)=r(r1)(r2)(rk+1)k!

when r is a real number. For example,

(1/24)=(1/2)(1/2)(3/2)(5/2)4!=5128and(23)=(2)(3)(4)3!=4.

These generalized binomial coefficients share some important properties of the usual binomial coefficients, most notably that

(rk)=(r1k1)+(r1k).

Then remarkably:

Theorem 3.2.1: Newton's Binomial Theorem

For any real number r that is not a non-negative integer, (x+1)r=i=0(ri)xi when 1<x<1.

Proof

It is not hard to see that the series is the Maclaurin series for (x+1)r, and that the series converges when 1<x<1. It is rather more difficult to prove that the series is equal to (x+1)r; the proof may be found in many introductory real analysis books.

Example 3.2.1

Expand the function (1x)n when n is a positive integer.

Solution

We first consider (x+1)n; we can simplify the binomial coefficients:

(n)(n1)(n2)(ni+1)i!=(1)i(n)(n+1)(n+i1)i!=(1)i(n+i1)!i!(n1)!=(1)i(n+i1i)=(1)i(n+i1n1).

Thus

(x+1)n=i=0(1)i(n+i1n1)xi=i=0(n+i1n1)(x)i.

Now replacing x by x gives (1x)n=i=0(n+i1n1)xi. So (1x)n is the generating function for (n+i1n1), the number of submultisets of {1,2,,n} of size i.

In many cases it is possible to directly construct the generating function whose coefficients solve a counting problem.

Example 3.2.2

Find the number of solutions to x1+x2+x3+x4=17, where 0x12, 0x25, 0x35, 2x46.

Solution

We can of course solve this problem using the inclusion-exclusion formula, but we use generating functions. Consider the function

(1+x+x2)(1+x+x2+x3+x4+x5)(1+x+x2+x3+x4+x5)(x2+x3+x4+x5+x6).

We can multiply this out by choosing one term from each factor in all possible ways. If we then collect like terms, the coefficient of xk will be the number of ways to choose one term from each factor so that the exponents of the terms add up to k. This is precisely the number of solutions to x1+x2+x3+x4=k, where 0x12, 0x25, 0x35, 2x46. Thus, the answer to the problem is the coefficient of x17. With the help of a computer algebra system we get

(1+x+x2)(1+x+x2+x3+x4+x5)2(x2+x3+x4+x5+x6)=x18+4x17+10x16+19x15+31x14+45x13+58x12+67x11+70x10+67x9+58x8+45x7+31x6+19x5+10x4+4x3+x2,

so the answer is 4.

Example 3.2.3

Find the generating function for the number of solutions to x1+x2+x3+x4=k, where 0x1, 0x25, 0x35, 2x46.

Solution

This is just like the previous example except that x1 is not bounded above. The generating function is thus

f(x)=(1+x+x2+)(1+x+x2+x3+x4+x5)2(x2+x3+x4+x5+x6)=(1x)1(1+x+x2+x3+x4+x5)2(x2+x3+x4+x5+x6)=(1+x+x2+x3+x4+x5)2(x2+x3+x4+x5+x6)1x.

Note that (1x)1=(1+x+x2+) is the familiar geometric series from calculus; alternately, we could use Example 3.2.1. Unlike the function in the previous example, this function has an infinite expansion:

f(x)=x2+4x3+10x4+20x5+35x6+55x7+78x8+102x9+125x10+145x11+160x12+170x13+176x14+179x15+180x16+180x17+180x18+180x19+180x20+.

Here is how to do this in Sage.

1f=(1+x+x^2+x^3+x^4+x^5)^2*(x^2+x^3+x^4+x^5+x^6)/(1-x)
2show(taylor(f,x,0,20))
Example 3.2.4

Find a generating function for the number of submultisets of {a,b,c} in which there are an odd number of as, an even number of bs, and any number of cs.

Solution

As we have seen, this is the same as the number of solutions to x1+x2+x3=n in which x1 is odd, x2 is even, and x3 is unrestricted. The generating function is therefore (x+x3+x5+)(1+x2+x4+)(1+x+x2+x3+)=x(1+(x2)+(x2)2+(x2)3+)(1+(x2)+(x2)2+(x2)3+)11x=x(1x2)2(1x).


This page titled 3.2: Newton's Binomial Theorem is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?