Sums, Products, and Binomial Coefficients

Summation notation $\displaystyle \sum_{i} a_i$ is used to denote a sum of terms; product notation $\displaystyle \prod_{i} a_i$ is used to denote a product of terms.

If n is a positive integer, n-factorial is $n! = 1\cdot 2\cdot \cdots \cdot n$ . By convention, .

Binomial coefficients are defined by $\displaystyle {n \choose k} = \dfrac{n!}{k!(n - k)!}$ .

In this section, I'll review the notation for sums and products, and give a brief introduction to binomial coefficients.

$\sum_{i=0}^n a_i \quad\hbox{means}\quad a_0 + a_1 + \cdots + a_n.$

That is, you replace the summation variable i with the numbers from 0 (the lower limit) to n (the upper limit), then sum the results.

Example.

$\sum_{i=0}^4 i^2 = 0^2 + 1^2 + 2^2 + 3^2 + 4^2 = 30.$

Your sums need not start at 0, and the summation variable can be anything you want:

$\sum_{i=2}^6 i\cdot b_i = 2b_2 + 3b_3 + 4b_4 + 5b_5 + 6b_6.$

$\sum_{j=1}^3 4 = 4 + 4 + 4 = 12.$

(If I replace j with 1, 2, and 3 in the expression "4", I get 4 three times.)

The following properties and those for products which are given below are fairly obvious, but careful proofs require mathematical induction (which I'll discuss later).

Proposition. ( Properties of sums)

(a) $\displaystyle \sum_{i=1}^n (a_i + b_i) = \sum_{i=1}^n a_i + \sum_{i=1}^n b_i$ .

(b) $\displaystyle \sum_{i=1}^n c\cdot a_i = c\cdot \sum_{i=1}^n a_i$ .

Example. If c is a constant, then

$\sum_{i=1}^n (a_i + c) = \sum_{i=1}^n a_i + \sum_{i=1}^n c = \sum_{i=1}^n a_i + n\cdot c.\quad\halmos$

$\prod_{i=0}^n a_i \quad\hbox{means}\quad a_0\cdot a_1\cdot \cdots \cdot a_n.$

That is, you replace the product variable i with the numbers from 0 (the lower limit) to n (the upper limit), then multiply the results.

Example.

$\prod_{i=1}^3 5 = 5\cdot 5 \cdot 5 = 125.$

(If I replace i with 1, 2, and 3 in the expression "5", I get 5 three times.)

Your products need not start at 0, and the product variable can be anything you want:

$\prod_{k=1}^n k = 1\cdot 2\cdot \cdots \cdot n.$

This is the product of the numbers from 1 to n. It comes up often enough that it has a special name and symbol; it's denoted and it's called n-factorial. For example,

$5! = 1\cdot 2\cdot 3\cdot 4\cdot 5 = 120.$

By convention, is defined to be 1.

Notice that

$n! = 1\cdot 2\cdot \cdots \cdot (n - 1) \cdot n = (n - 1)! \cdot n.$

is defined if n is a nonnegative integer; can you define if n is not an integer? For example, what would $\dfrac{1}{2}!$ be?

In math, you can define things in many ways, but some ways are more useful than others. In this case, you'd want the "extended" definition of to agree with the old one when n is a nonnegative integer. It would also be nice for the equation $n! = (n - 1)! \cdot n$ to hold.

There is a way of defining the "factorial" of any positive real number so that these conditions (and others involving the defining function) hold. The Gamma function is defined by

$\Gamma(x) = \int_0^\infty e^{-t} t^{x-1}\,dt \quad \hbox{for} \quad x > 0.$

(Note that x here is a real number.) If n is a positive integer,

$\Gamma(n + 1) = n!.$

Here's a graph of the Gamma function:

$\hbox{\epsfysize=1.75in \epsffile{summation1.eps}}$

I've placed dots at the points so you can see that the Gamma function really goes through the factorial points. Note also that $\Gamma(1) = 1$ . But if I plug into the formula above, I get $\Gamma(0 + 1) = 0!$ , i.e. $\Gamma(1) = 0!$ . Thus, , which is the convention I mentioned earlier.

Proposition. ( Properties of products)

(a) $\displaystyle \prod_{i=1}^n a_ib_i = \left(\prod_{i=1}^n a_i\right)\left(\prod_{i=1}^n b_i\right)$ .

(b) $\displaystyle \prod_{i=1}^n a_i^k = \left(\prod_{i=1}^n a_i\right)^k$ .

Example.

$\prod_{i=1}^n (ca_i)^2 = \prod_{i=1}^n c^2a_i^2 = \left(\prod_{i=1}^n c^2\right)\left(\prod_{i=1}^n a_i^2\right) = c^{2n}\left(\prod_{i=1}^n a_i\right)^2.\quad\halmos$

Binomial coefficients are defined in terms of factorials. If n and k are integers, $n \ge 0$ , and $0 \le k \le n$ , then

${n \choose k} = \dfrac{n!}{k!\,(n - k)!}.$

The expression on the left is read n-choose-k.

Example.

${5 \choose 3} = \dfrac{5!}{3!\,2!} = \dfrac{1\cdot 2\cdot 3\cdot 4\cdot 5} {1\cdot 2\cdot 3\cdot 1\cdot 2} = \dfrac{4\cdot 5}{1\cdot 2} = 10.\quad\halmos$

Proposition. ( Properties of binomial coefficients)

(a) $\displaystyle {n \choose n} = {n \choose 0} = 1$ .

(b) $\displaystyle {n \choose k} = {n \choose {n-k}}$ .

The last property has the following pictorial interpretation.

$\hbox{\epsfysize=2in \epsffile{summation2.eps}}$

Make a triangle as shown by starting at the top and writing 1's down the sides. Then fill in the middle of the triangle one row at a time, by adding the elements diagonally above the new element. For example, the leftmost 4 in the row was obtained this way:

$\matrix{1 & & & & 3 \cr & \searrow & & \swarrow & \cr & & 4 & & \cr}$

The formula above is simply an algebraic expression of this addition procedure.

Proof. You can check the formulas in (a) and (b) by writing out the binomial coefficients. Here's the computation for one part of (a):

${n \choose n} = \dfrac{n!}{n!\,0!} = 1.$

And here's the computation for (b):

${n \choose k} = \dfrac{n!}{k!\,(n - k)!} = \dfrac{n!}{(n - k)!\,k!} = {n \choose {n-k}}.$

The proof of (c) is also a computation, though it's a little more involved:

${n \choose k} + {n \choose {k-1}} = \dfrac{n!}{k!\,(n - k)!} + \dfrac{n!}{(k - 1)!\,(n - k + 1)!} = \dfrac{n!}{(k - 1)!\,(n - k)!} \left(\dfrac{1}{k} + \dfrac{1}{n - k + 1}\right) =$

$\dfrac{n!}{(k - 1)!\,(n - k)!}\cdot \dfrac{(n - k + 1) + k}{k(n - k + 1)} = \dfrac{n!}{(k - 1)!\,(n - k)!}\cdot \dfrac{n + 1}{k(n - k + 1)} = \dfrac{(n + 1)!}{k!\,(n - k + 1)!}.\quad\halmos$

Of course, binomial coefficients get their name because they're the coefficients in the expansion of a binomial:

$(x + y)^n = \sum_{k=0}^n {n \choose k}x^ky^{n-k}.$

Since the coefficients can be read off from Pascal's triangle, you can use the triangle to write down binomial expansions.

Example. Using the row in the triangle, I get

$(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4.\quad\halmos$

Example. Determine the coefficient of $x^{37}y^3$ in the expansion of $(2x - 3y)^{40}$ .

The term containing $x^{37}y^3$ is

${40 \choose 37}(2x)^{37}(-3y)^3 = \dfrac{40!}{37!3!}2^{37}(-3)^3x^{37}y^3 = -38\cdot 39\cdot 40\cdot 2^{36}\cdot 3^2\cdot x^{37}y^3.$

(I cancelled the with the first 37 terms in , then cancelled the $3! = 3\cdot 2$ with $2^{37}$ and .) The coefficient is $-38\cdot 39\cdot 40\cdot 2^{36}\cdot 3^2$ , or -36663215228190720 if you multiply it out.

Send comments about this page to: bikenaga@marauder.millersville.edu.

Last updated: June 7, 2008

Bruce Ikenaga's Home Page

Math Department Home Page

Millersville University Home Page