$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.2: Newton's Binomial Theorem

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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

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.

f=(1+x+x^2+x^3+x^4+x^5)^2*(x^2+x^3+x^4+x^5+x^6)/(1-x)
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