3.2: Newton's Binomial Theorem

Recall that

$${n\choose k}={n!\over k!\,(n-k)!}={n(n-1)(n-2)\cdots(n-k+1)\over k!}.\nonumber$$

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

$${r\choose k}={r(r-1)(r-2)\cdots(r-k+1)\over k!}\nonumber$$

when $r$ is a real number. For example,

$${1/2\choose 4}={(1/2)(-1/2)(-3/2)(-5/2)\over 4!}={-5\over128} \quad\hbox{and}\quad {-2\choose 3}={(-2)(-3)(-4)\over 3!}=-4. \nonumber$$

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

$$\label{eq:1}\eqalignno{ {r\choose k}&={r-1\choose k-1}+{r-1\choose k}.\cr }$$

Then remarkably:

Theorem $\PageIndex{1}$: Newton's Binomial Theorem

For any real number $r$ that is not a non-negative integer, $$(x+1)^r=\sum_{i=0}^\infty {r\choose i}x^i\nonumber$$ 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 $\PageIndex{1}$

Expand the function $(1-x)^{-n}$ when $n$ is a positive integer.

Solution

We first consider $(x+1)^{-n}$; we can simplify the binomial coefficients:

$$\eqalign{ {(-n)(-n-1)(-n-2)\cdots(-n-i+1)\over i!} &=(-1)^i{(n)(n+1)\cdots(n+i-1)\over i!}\cr &=(-1)^i{(n+i-1)!\over i!\,(n-1)!}\cr &=(-1)^i{n+i-1\choose i}=(-1)^i{n+i-1\choose n-1}.\cr }\nonumber$$

Thus

$$(x+1)^{-n}=\sum_{i=0}^\infty (-1)^i{n+i-1\choose n-1}x^i =\sum_{i=0}^\infty {n+i-1\choose n-1}(-x)^i.\nonumber$$

Now replacing $x$ by $-x$ gives $$(1-x)^{-n}=\sum_{i=0}^\infty {n+i-1\choose n-1}x^i.\nonumber$$ So $(1-x)^{-n}$ is the generating function for ${n+i-1\choose n-1}$, the number of submultisets of $\{\infty\cdot1,\infty\cdot2,\ldots,\infty\cdot n\}$ of size $i$.

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

Example $\PageIndex{2}$

Find the number of solutions to $\displaystyle x_1+x_2+x_3+x_4=17$, where $0\le x_1\le2$, $0\le x_2\le5$, $0\le x_3\le5$, $2\le x_4\le6$.

Solution

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

$$(1+x+x^2)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4+x^5)(x^2+x^3+x^4+x^5+x^6).\nonumber$$

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 $x^k$ 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 $\displaystyle x_1+x_2+x_3+x_4=k$, where $0\le x_1\le2$, $0\le x_2\le5$, $0\le x_3\le5$, $2\le x_4\le6$. Thus, the answer to the problem is the coefficient of $x^{17}$. With the help of a computer algebra system we get

$$\eqalign{ (1+x+x^2)(1&+x+x^2+x^3+x^4+x^5)^2(x^2+x^3+x^4+x^5+x^6)\cr =\;&x^{18} + 4x^{17} + 10x^{16} + 19x^{15} + 31x^{14} + 45x^{13} + 58x^{12} + 67x^{11} + 70x^{10}\cr &+67x^9 + 58x^8 + 45x^7 + 31x^6 + 19x^5 + 10x^4 + 4x^3 + x^2,\cr }\nonumber$$

so the answer is 4.

Example $\PageIndex{3}$

Find the generating function for the number of solutions to $\displaystyle x_1+x_2+x_3+x_4=k$, where $0\le x_1\le\infty$, $0\le x_2\le5$, $0\le x_3\le5$, $2\le x_4\le6$.

Solution

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

$$\eqalign{ f(x)&=(1+x+x^2+\cdots)(1+x+x^2+x^3+x^4+x^5)^2(x^2+x^3+x^4+x^5+x^6)\cr &=(1-x)^{-1}(1+x+x^2+x^3+x^4+x^5)^2(x^2+x^3+x^4+x^5+x^6)\cr &={(1+x+x^2+x^3+x^4+x^5)^2(x^2+x^3+x^4+x^5+x^6)\over 1-x}. }\nonumber$$

Note that $(1-x)^{-1}=(1+x+x^2+\cdots)$ is the familiar geometric series from calculus; alternately, we could use Example $\PageIndex{1}$. Unlike the function in the previous example, this function has an infinite expansion:

$$\eqalign{ f(x)&= x^2+4x^3 + 10x^4 + 20x^5 +35x^6 + 55x^7+ 78x^8 \cr &+ 102x^9 + 125x^{10}+ 145x^{11} + 160x^{12} + 170x^{13}+176x^{14} \cr &+ 179x^{15} +180x^{16} + 180x^{17} + 180x^{18} + 180x^{19} + 180x^{20} +\cdots. }\nonumber$$

Here is how to do this in Sage.

view sourceprint?

1	f=(1+x+x^2+x^3+x^4+x^5)^2*(x^2+x^3+x^4+x^5+x^6)/(1-x)

2	show(taylor(f,x,0,20))

Example $\PageIndex{4}$

Find a generating function for the number of submultisets of $\{\infty\cdot a,\infty\cdot b,\infty\cdot c\}$ in which there are an odd number of $a$s, an even number of $b$s, and any number of $c$s.

Solution

As we have seen, this is the same as the number of solutions to $x_1+x_2+x_3=n$ in which $x_1$ is odd, $x_2$ is even, and $x_3$ is unrestricted. The generating function is therefore $$\eqalign{ (x+x^3+x^5&+\cdots)(1+x^2+x^4+\cdots)(1+x+x^2+x^3+\cdots)\cr &=x(1+(x^2)+(x^2)^2+(x^2)^3+\cdots)(1+(x^2)+(x^2)^2+(x^2)^3+\cdots){1\over 1-x}\cr &={x\over (1-x^2)^2(1-x)}.\cr }\nonumber$$