Induction and Sequences

Sequences as Indexed Lists

A sequence gives a real number for each index in a specified set. Induction is a natural tool for proving claims about sequences because the index advances one integer at a time. A statement about a sequence might concern the value of each term, a sum of the first several terms, or a comparison between two sequences. In each case, induction turns a claim about all indices into a starting check and a step from one index to the next.

Definition (Real sequence). A real sequence indexed by \(\mathbb{N}_0\) is a function from \(\mathbb{N}_0\) to \(\mathbb{R}\). Its value at \(n\) is called its \(n\)th term and is commonly written \(a_n\). The sequence itself is written \((a_n)_{n=0}^{\infty}\), or simply \((a_n)\) when the index range is clear.

For example, the rule \(a_n=4n-1\) specifies a sequence: \(a_0=-1\), \(a_1=3\), and \(a_2=7\). The index is part of the notation. A sequence can also be indexed starting at \(1\), or at another integer; its starting index must be stated when it matters.

The first \(n\) terms of a sequence indexed by \(\mathbb{N}_0\) are \(a_0,a_1,\ldots,a_{n-1}\). Their sum is called a partial sum. We use the empty-sum convention when \(n=0\), so the sum of the first zero terms is \(0\). This convention often makes a formula for partial sums valid at its starting index.

S_n=\sum_{k=0}^{n-1}a_k,\qquad S_0=0.

A statement about a sequence is proved by induction in the same way as any other statement indexed by the nonnegative integers. The key is to identify precisely what \(P(n)\) says. For a partial-sum formula, for instance, \(P(n)\) should state that the sum of the first \(n\) terms equals the proposed expression. The Principle of Mathematical Induction then applies once the base case and the implication from \(P(n)\) to \(P(n+1)\) have been proved.

Partial Sums of an Arithmetic Sequence

An arithmetic sequence has a fixed difference between consecutive terms. Consider a sequence indexed by \(\mathbb{N}_0\) whose terms are \(a_k=a+kd\), where \(a,d\in\mathbb{R}\). The first term is \(a\), the next is \(a+d\), and each subsequent term increases by \(d\) (or decreases by \(d\) if \(d<0\)). The following formula gives the sum of its first \(n\) terms, including the case \(n=0\).

Theorem (Partial sums of an arithmetic sequence). Let \(a,d\in\mathbb{R}\), and define \(a_k=a+kd\) for every \(k\in\mathbb{N}_0\). For every \(n\in\mathbb{N}_0\),

\sum_{k=0}^{n-1}(a+kd)=na+\frac{dn(n-1)}{2},

where the sum is empty and equals \(0\) when \(n=0\).

Proof. Let \(P(n)\) be the stated formula. At \(n=0\), both the empty sum and the right-hand side equal \(0\):

\sum_{k=0}^{-1}(a+kd)=0 \qquad\text{and}\qquad 0a+\frac{d\cdot0\cdot(-1)}{2}=0.

Now suppose \(P(n)\) holds for some \(n\in\mathbb{N}_0\). The sum of the first \(n+1\) terms is the sum of the first \(n\) terms together with the next term, \(a+nd\). Therefore, using the inductive hypothesis,

\begin{aligned} \sum_{k=0}^{n}(a+kd) &=\sum_{k=0}^{n-1}(a+kd)+(a+nd)\\ &=na+\frac{dn(n-1)}{2}+a+nd\\ &=(n+1)a+\frac{dn(n-1)+2nd}{2}\\ &=(n+1)a+\frac{dn(n+1)}{2}. \end{aligned}

This is the required formula with \(n+1\) in place of \(n\), since \[ \frac{d(n+1)n}{2}=\frac{dn(n+1)}{2}. \] Thus \(P(n)\) implies \(P(n+1)\). The Principle of Mathematical Induction proves the formula for every \(n\in\mathbb{N}_0\). \(\square\)

Worked Example: Summing an Arithmetic Sequence

Let \(a_k=7+3k\). The first five terms, whose indices are \(0\) through \(4\), are

a_0=7,\qquad a_1=10,\qquad a_2=13,\qquad a_3=16,\qquad a_4=19.

Here \(a=7\), \(d=3\), and \(n=5\). The theorem gives

\sum_{k=0}^{4}(7+3k) =5\cdot7+\frac{3\cdot5\cdot4}{2} =35+30 =65.

Direct addition checks the result: \[ 7+10+13+16+19=17+13+16+19=30+16+19=46+19=65. \] The formula works without having to add each term separately, and induction guarantees it for every number of terms, not only five.

A Formula for the Sum of Squares

Sequences can also be used to express familiar finite sums. The sequence \(a_k=k^2\), for \(k\in\mathbb{N}_0\), begins \(0,1,4,9,16,\ldots\). Its partial sums have a formula that is particularly useful because the next sum is obtained by adding one square.

Theorem (Sum of the first squares). For every \(n\in\mathbb{N}_0\),

\sum_{k=0}^{n-1}k^2=\frac{n(n-1)(2n-1)}{6},

where the sum is empty and equals \(0\) when \(n=0\).

Proof. Let \(P(n)\) be the displayed identity. When \(n=0\), the sum is empty and the right-hand side is \[ \frac{0\cdot(-1)\cdot(-1)}{6}=0, \] so \(P(0)\) holds. Suppose \(P(n)\) holds for some \(n\in\mathbb{N}_0\). Add the next term, \(n^2\), to the sum:

\begin{aligned} \sum_{k=0}^{n}k^2 &=\sum_{k=0}^{n-1}k^2+n^2\\ &=\frac{n(n-1)(2n-1)}{6}+n^2\\ &=\frac{n(n-1)(2n-1)+6n^2}{6}\\ &=\frac{n\bigl((n-1)(2n-1)+6n\bigr)}{6}\\ &=\frac{n(2n^2+3n+1)}{6}\\ &=\frac{n(n+1)(2n+1)}{6}. \end{aligned}

The last expression is the claimed formula with \(n+1\) substituted for \(n\), because \[ \frac{(n+1)n(2(n+1)-1)}{6} =\frac{n(n+1)(2n+1)}{6}. \] Thus \(P(n)\) implies \(P(n+1)\). The Principle of Mathematical Induction proves the identity for every \(n\in\mathbb{N}_0\). \(\square\)

Worked Example: Adding the First Five Squares

The first five terms of the square sequence \(k^2\) have indices \(0\) through \(4\). Applying the theorem with \(n=5\) gives

\sum_{k=0}^{4}k^2 =\frac{5\cdot4\cdot9}{6} =20\cdot\frac{9}{6} =30.

The terms themselves confirm this: \[ 0^2+1^2+2^2+3^2+4^2=0+1+4+9+16=30. \] The index convention is important: \(n=5\) means five terms, ending at index \(4\), not at index \(5\). If the sum instead ran from \(0\) through \(5\), it would contain six terms and equal \(30+5^2=55\).

Comparing Two Sequences by Induction

Another common sequence claim compares corresponding terms. It may assert that \(a_n\leq b_n\) for every index in a stated range. Such a claim requires both an appropriate base index and an inductive step that preserves the inequality. The starting index can be crucial: a comparison may be false for early terms and true from some later term onward.

Theorem (A quadratic sequence is eventually bounded by an exponential sequence). For every integer \(n\geq4\),

n^2\leq 2^n.

Proof. At \(n=4\), both sides equal \(16\), so the claim holds. Suppose \(n\geq4\) and \(n^2\leq2^n\). First, \(n^2\leq2n^2\), since \(n^2\geq0\). Also,

2n^2\leq(n+1)^2

is not the inequality needed here, so we instead compare \((n+1)^2\) directly with \(2n^2\). Since \(n\geq4\),

2n^2-(n+1)^2=n^2-2n-1=n(n-2)-1\geq4\cdot2-1=7>0.

Therefore \((n+1)^2\leq2n^2\). Combining this with the inductive hypothesis gives

(n+1)^2\leq2n^2\leq2\cdot2^n=2^{n+1}.

This proves the step from \(n\) to \(n+1\). By induction starting at \(4\), \(n^2\leq2^n\) for every integer \(n\geq4\). \(\square\)

Worked Example: Comparing Terms at a Chosen Index

The theorem can be applied at \(n=7\), which is within its stated range. The two sequence terms are

7^2=49 \qquad\text{and}\qquad 2^7=128,

so \(49\leq128\), as claimed. The range \(n\geq4\) cannot simply be replaced by \(n\geq0\): at \(n=2\), the comparison would say \(4\leq4\), which is true, but at \(n=3\), it says \(9\leq8\), which is false. The proved starting index matters even when some earlier indices happen to satisfy the claim.

Reading the Index Carefully

Induction proofs about sequences often fail through an indexing mismatch rather than difficult algebra. A term \(a_n\) is one value; a partial sum \(\sum_{k=0}^{n-1}a_k\) contains \(n\) terms. Adding the next term changes the upper index from \(n-1\) to \(n\), which is why the new partial sum is written \(\sum_{k=0}^{n}a_k\). Likewise, if a claim begins at \(n=4\), the base case is \(P(4)\), and the inductive step must assume \(P(n)\) for an arbitrary \(n\geq4\).

The algebra in the step should reflect the structure of the sequence. For a partial sum, separate off exactly one new term. For a comparison, find an inequality that relates the next term to the current one, then combine it with the inductive hypothesis. Checking a few values can help reveal a plausible formula or a necessary starting index, but finitely many checks do not prove a claim for every index.

Specify the sequence and index range.
State how each term is defined and where the claim is meant to hold.

Write the exact statement at index \(n\).
Distinguish a claim about one term from a claim about a sum of terms.

Check the correct base case.
Substitute the starting index into both sides, including the empty-sum case when appropriate.

Relate consecutive indices.
For partial sums, add the next term; for inequalities, establish the comparison needed at the next index.

Apply induction.
Verify that the argument works for an arbitrary index in the stated range, then conclude the claim throughout that range.

Key takeaway. A sequence claim is a statement about indexed terms. Induction proves such claims by checking the correct starting index and establishing a valid step to the next index; careful notation keeps term formulas and partial-sum formulas aligned.

Check Your Understanding

Use the definitions and induction arguments in this tutorial to answer the following questions.

What is a real sequence indexed by \(\mathbb{N}_0\), and what does \(a_n\) denote?
How many terms are included in \(\sum_{k=0}^{n-1}a_k\) when \(n\geq1\)? What is its value when \(n=0\)?
For the arithmetic sequence \(a_k=5+2k\), use the partial-sum formula to find the sum of the first four terms.
In the proof of the sum-of-squares formula, what term is added when passing from the sum through \(n-1\) to the sum through \(n\)?
Why does the theorem \(n^2\leq2^n\) begin at \(n=4\), and which comparison between \((n+1)^2\) and \(2n^2\) is used in its inductive step?

What You'll Learn