Induction and Products

From Sums to Products

In the previous tutorial, induction was used to prove formulas for finite sums. A product has a similar endpoint structure: when the upper limit increases from $n$ to $n+1$, the product gains one factor. The important difference is that the new factor is multiplied by the earlier product rather than added to it.

This change can make product proofs feel unfamiliar at first, especially when the expression at $n+1$ must be simplified. The reliable approach is to write the new endpoint factor explicitly, substitute the inductive hypothesis, and then simplify. Keeping the limits and the new factor visible helps prevent common indexing errors.

Definition (Finite product). For integers $m\leq n$, the notation $\prod_{k=m}^{n} a_k$ means the product $a_m a_{m+1}\cdots a_n$. If the lower limit exceeds the upper limit, the product is defined to be $1$, called the empty product.

The empty product is assigned the value $1$ because multiplying by $1$ leaves any product unchanged. It also gives a natural base case for many product formulas. For instance, $\prod_{k=1}^{0}a_k=1$, whereas $\prod_{k=0}^{0}a_k=a_0$ contains one factor. As with sums, the limits determine which terms are included.

The Endpoint Relation for Products

By the definition of a finite product, the product through $n+1$ consists of the product through $n$, multiplied by the factor with index $n+1$:

\prod_{k=m}^{n+1}a_k = \left(\prod_{k=m}^{n}a_k\right)a_{n+1}, \qquad m\leq n+1.

This relation is the basic move in an inductive proof about products. When $m=n+1$, it holds because the product through $n$ is empty and equals $1$. The order of the factors does not affect their product, so the endpoint factor may be written on either side. The proof must still account for that factor exactly once.

State the product claim.
Record the index range and the proposed expression for the product.

Check the base case.
Evaluate the product at the starting index, including the empty-product convention if applicable.

Include the new factor.
Rewrite the product through $n+1$ as the product through $n$ multiplied by $a_{n+1}$.

Use the inductive hypothesis.
Replace the product through $n$ with its claimed expression and simplify to the target at $n+1$.

Conclude by induction.
Once the base case and inductive step are proved, apply the Principle of Mathematical Induction.

Products and Factorials

Factorials are a familiar way to record products of consecutive positive integers. Define $0!=1$, and for each positive integer $n$, define $n!=1\cdot2\cdots n$. The endpoint relation immediately gives the factorial recurrence.

Theorem (Factorial Product and Recurrence). For every $n\in\mathbb{N}_0$, $$ \prod_{k=1}^{n}k=n!, $$ where the product is empty when $n=0$. In particular, for every $n\in\mathbb{N}_0$, $$ (n+1)!=(n+1)n!. $$

Proof. At $n=0$, the product is empty and equals $1$, which is $0!$ by definition. Now let $n\in\mathbb{N}_0$ and assume $\prod_{k=1}^{n}k=n!$. The endpoint relation gives

\prod_{k=1}^{n+1}k = \left(\prod_{k=1}^{n}k\right)(n+1) = n!(n+1) = (n+1)!.

The final equality is the defining factorial recurrence. Thus the product identity holds at $n+1$, and induction proves it for every $n\in\mathbb{N}_0$. The recurrence also follows directly by separating the last factor in the defining product. $\square$

Worked Example: Calculating a Factorial Product

Evaluate $\prod_{k=1}^{7}k$. By the factorial product identity and recurrence,

\prod_{k=1}^{7}k = 7! = 7\cdot6! = 7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1 = 5040.

The endpoint is $7$, so the factors are precisely $1,2,3,4,5,6,7$. For comparison, the product with upper limit $6$ is $6!=720$, and including the new factor gives $7\cdot720=5040$, as the recurrence requires.

A Telescoping Product

In a telescoping sum, neighboring terms cancel through addition and subtraction. A telescoping product works by cancellation of common factors in numerators and denominators. The following identity can also be proved directly by induction, making it a useful model for the product endpoint step.

Theorem (A Basic Telescoping Product). For every $n\in\mathbb{N}_0$, $$ \prod_{k=1}^{n}\left(1+\frac{1}{k}\right)=n+1. $$

Proof. At $n=0$, the product is empty and equals $1$, which is also $0+1$. Suppose the identity holds for some $n\in\mathbb{N}_0$. The endpoint relation and the inductive hypothesis give

\prod_{k=1}^{n+1}\left(1+\frac{1}{k}\right) = \left(\prod_{k=1}^{n}\left(1+\frac{1}{k}\right)\right) \left(1+\frac{1}{n+1}\right) = (n+1)\left(\frac{n+2}{n+1}\right) = n+2.

Here $n+1$ is positive, so cancellation is valid. The final expression is the claimed value at $n+1$. By the Principle of Mathematical Induction, the identity holds for every $n\in\mathbb{N}_0$. $\square$

Worked Example: Evaluating a Telescoping Product

For $n=5$, the theorem gives a quick evaluation:

\prod_{k=1}^{5}\left(1+\frac{1}{k}\right) = 2\cdot\frac32\cdot\frac43\cdot\frac54\cdot\frac65 = 6.

Each factor has the form $(k+1)/k$, so the full product is

\frac21\cdot\frac32\cdot\frac43\cdot\frac54\cdot\frac65.

The factors $2,3,4,5$ in the numerators cancel with the matching factors in the denominators, leaving $6/1=6$. This agrees with $n+1=5+1=6$. The cancellation works because all denominators are nonzero.

Products of Powers

A product can also have factors that are themselves powers. When the base is $2$, the exponents in the product are the consecutive integers from $0$ to $n$. The formula below gives the resulting power as a single expression.

Theorem (Product of Powers of Two). For every $n\in\mathbb{N}_0$, $$ \prod_{k=0}^{n}2^k=2^{n(n+1)/2}. $$

Proof. At $n=0$, the left side is $2^0=1$, and the right side is $2^{0(0+1)/2}=2^0=1$. Now suppose the identity holds for some $n\in\mathbb{N}_0$. Adding the next endpoint factor gives

\prod_{k=0}^{n+1}2^k = \left(\prod_{k=0}^{n}2^k\right)2^{n+1} = 2^{n(n+1)/2}2^{n+1} = 2^{n(n+1)/2+n+1}.

The exponent simplifies as follows:

\frac{n(n+1)}{2}+n+1 = \frac{n(n+1)+2(n+1)}{2} = \frac{(n+1)(n+2)}{2}.

Therefore $\prod_{k=0}^{n+1}2^k=2^{(n+1)(n+2)/2}$, the claimed formula with $n+1$ in place of $n$. Induction proves the result for every $n\in\mathbb{N}_0$. $\square$

Worked Example: Multiplying Consecutive Powers of Two

Evaluate $\prod_{k=0}^{4}2^k$. The theorem gives

\prod_{k=0}^{4}2^k = 2^{4(4+1)/2} = 2^{10} = 1024.

The factors themselves are $2^0,2^1,2^2,2^3,2^4$, so direct multiplication confirms the result:

1\cdot2\cdot4\cdot8\cdot16 = 2\cdot4\cdot8\cdot16 = 8\cdot8\cdot16 = 64\cdot16 = 1024.

There are five factors, but their exponents add to $0+1+2+3+4=10$. The exponent in the formula records that total.

Shifting the Factors

The same cancellation idea applies when the numerator and denominator differ by more than one. Consider the product with factors $1+2/k$. Since $1+2/k=(k+2)/k$, most of the numerator and denominator factors cancel.

Worked Example: A Product with a Two-Unit Shift

For $n=4$, rewrite and evaluate each factor:

\prod_{k=1}^{4}\left(1+\frac{2}{k}\right) = \frac31\cdot\frac42\cdot\frac53\cdot\frac64 = 3\cdot2\cdot\frac53\cdot\frac32 = 15.

In the unsimplified product, the numerator factors are $3,4,5,6$ and the denominator factors are $1,2,3,4$. The $3$ and $4$ cancel, leaving $5\cdot6/(1\cdot2)=30/2=15$. More generally, for $n\geq1$, the same cancellation gives

\prod_{k=1}^{n}\left(1+\frac{2}{k}\right) = \frac{3\cdot4\cdots(n+2)}{1\cdot2\cdots n} = \frac{(n+1)(n+2)}{2}.

Indeed, the numerator consists of the integers from $3$ through $n+2$, while the denominator consists of those from $1$ through $n$. For $n\geq3$, the common factors $3,\ldots,n$ cancel, leaving numerator factors $n+1$ and $n+2$ and denominator factors $1$ and $2$. For $n=1$, the product is $3/1=3=(1+1)(1+2)/2$; for $n=2$, it is $(3\cdot4)/(1\cdot2)=6=(2+1)(2+2)/2$. For $n=4$, this formula gives $5\cdot6/2=15$, in agreement with the direct calculation.

What to Watch For

The product endpoint relation is simple, but several errors are easy to make. First, the new factor has index $n+1$, not $n$. Second, an empty product equals $1$, not $0$; using the sum convention for a product would make many base cases false. Finally, cancellation is permitted only for nonzero factors in denominators. In the telescoping example, the denominators are positive integers, so none is zero.

Products are also sensitive to whether a factor is zero. The endpoint relation itself remains valid even if some factor is zero, but a proof that divides by a factor must establish that the factor is nonzero. The product of powers of two avoids this issue because every factor is positive. A reliable proof makes any needed cancellation explicit rather than treating it as automatic.

Key takeaway. When the upper limit of a product increases from $n$ to $n+1$, multiply the product through $n$ by the single new factor $a_{n+1}$. Check the base case using the empty-product convention, and verify that any cancellation in the algebra uses nonzero factors.

Check Your Understanding

Use the endpoint relation and the examples above to answer the following questions.

What value is assigned to a product with no factors, and why is that convention useful?
What factor is added when the upper limit of $\prod_{k=m}^{n}a_k$ changes from $n$ to $n+1$?
Use the factorial recurrence to express $8!$ in terms of $7!$.
In the telescoping product $\prod_{k=1}^{n}(1+1/k)$, which factors cancel, and what remains?
Why is the exponent in $\prod_{k=0}^{n}2^k$ equal to $n(n+1)/2$?

What You'll Learn