Lesson 16: Sequences, Series, and Mathematical Induction

Sequences are functions whose domain is the positive integers; series are their sums. This lesson treats them together with the proof technique that belongs to them: mathematical induction, the rigorous way to prove a statement for all n at once. Induction is often a student's first real proof method, and calculus will lean on it for series and error bounds.

Arithmetic and geometric sequences

An arithmetic sequence has a_n = a + (n − 1)d; a geometric sequence has a_n = a·r^(n − 1). Worked examples. Arithmetic with a = 7, d = 5: a_20 = 7 + 19·5 = 102, and S_20 = (20/2)(7 + 102) = 1090. Geometric with a = 3, r = 2: a_8 = 3·2^7 = 384, S_8 = 3(2^8 − 1)/(2 − 1) = 765. The formulas from Lesson 10 return here because sequences and series are two views of one object: the sequence is the list, the series is its running total. Read problems for which view is asked — "the 20th term" and "the sum of 20 terms" differ by exactly the formula choice.

Recursive sequences

A recursive definition gives starting values and a rule in terms of previous terms. Fibonacci: a_1 = a_2 = 1, a_n = a_{n−1} + a_{n−2} gives 1, 1, 2, 3, 5, 8, 13, ... Worked example — from recursive to explicit: a_1 = 2, a_n = 3a_{n−1} − 1 gives 2, 5, 14, 41. The fixed point L satisfies L = 3L − 1, so L = 1/2; subtracting, a_n − 1/2 = 3(a_{n−1} − 1/2), so a_n − 1/2 is geometric with ratio 3: a_n = 1/2 + (3/2)·3^(n−1) = (3^n + 1)/2. Check n = 4: (81 + 1)/2 = 41 ✓. Not every recurrence has a neat closed form (Fibonacci's involves the golden ratio), but *computing* terms recursively and *recognising* the pattern is a universally available strategy — and the pattern claim is then proved by induction.

Sigma notation

Σ_{k=1}^{n} a_k compresses a sum; the index k is a dummy variable and the bounds are part of the meaning. Worked example: Σ_{k=1}^{5} (2k − 1) = 1 + 3 + 5 + 7 + 9 = 25 — the first five odd numbers sum to 5^2, an instance of the theorem Σ_{k=1}^{n} (2k − 1) = n^2 that we prove below. Changing bounds shifts sums predictably, and splitting Σ(a_k + b_k) = Σa_k + Σb_k is legal (sums distribute); splitting Σ(a_k·b_k) is not.

Mathematical induction

To prove a statement P(n) for all integers n ≥ n_0: (1) Base case: verify P(n_0) directly. (2) Inductive step: assume P(k) (the inductive hypothesis) and prove P(k + 1), using the assumption. Then P holds for all n ≥ n_0 — dominoes: the base case knocks the first, the step guarantees each knocks the next.

Worked proof 1 — a sum formula. Claim: Σ_{k=1}^{n} k = n(n + 1)/2. Base (n = 1): LHS = 1, RHS = 1·2/2 = 1 ✓. Step: assume Σ_{k=1}^{m} k = m(m + 1)/2. Then Σ_{k=1}^{m+1} k = m(m + 1)/2 + (m + 1) = (m + 1)(m/2 + 1) = (m + 1)(m + 2)/2 — the formula with n = m + 1. ∎

Worked proof 2 — divisibility. Claim: 3 divides n^3 − n for all n ≥ 1. Base: 1 − 1 = 0, divisible by 3 ✓. Step: assume 3 | (k^3 − k). Expand (k + 1)^3 − (k + 1) = k^3 + 3k^2 + 3k + 1 − k − 1 = (k^3 − k) + 3(k^2 + k). The first bracket is divisible by 3 by the hypothesis, the second is an explicit multiple of 3; a sum of multiples of 3 is a multiple of 3. ∎ (The same proof shape proves Σ of odds = n^2: k^2 + (2k + 1) = (k + 1)^2.) Induction can also start above 1: 2^n > n^2 holds for n ≥ 5 (base 32 > 25; the step uses 2k^2 ≥ (k + 1)^2 once k ≥ 3).

Modelling: training plans and growth

Application — arithmetic training. A runner covers 2 km on day 1 and adds 0.3 km each day. Day 30 distance: 2 + 29(0.3) = 10.7 km; total over the month: S_30 = (30/2)(2 + 10.7) = 15 × 12.7 = 190.5 km. Coaches plan with arithmetic sequences precisely because the *sum* (total load) is as important as the daily term (peak load), and both formulas are needed to keep athletes progressing without injury. Loan payments, depreciation schedules and dose tapering are the same arithmetic — geometric versions model compound growth and decay, closing the loop with Lesson 3.

Common mistakes

• Proving the inductive step backwards. Writing the P(k + 1) statement and simplifying it into P(k) assumes what you must prove. Start from one side of P(k + 1), use P(k), and arrive at the other side.
• Skipping the base case. The step alone is not enough: the "proof" that all horses are the same colour has a valid-looking step and a broken base/overlap. Conversely, a base case without the step proves one instance, not a theorem.
• Off-by-one in a_n. The nth term is a + (n − 1)d because the first term has absorbed zero differences. Checking with n = 1 (formula must return a) catches this instantly.
• Confusing a_n and S_n in applications. Total distance uses S_n; the distance on a given day uses a_n. In the training example: 1090-type numbers come from sums, 102-type numbers from terms — mixing them inflates training load eleven-fold.
• Treating Σ bounds casually. Σ_{k=0}^{4} 2^k = 31 has five terms; Σ_{k=1}^{4} 2^k = 30 has four. The lower bound is part of the sum.

Exam Experience

1. The 30th term of the arithmetic sequence 5, 9, 13, ... is

• (A) 117
• (B) 121
• (C) 125
• (D) 113

Answer: (B). a_30 = 5 + 29·4 = 5 + 116 = 121. (A) uses 28 differences (the (n − 1) slip); (C) uses 30.

2. Σ_{k=1}^{4} k^2 =

• (A) 20
• (B) 30
• (C) 16
• (D) 100

Answer: (B). 1 + 4 + 9 + 16 = 30. (D) is (1 + 2 + 3 + 4)^2 = 100 — squaring the sum instead of summing the squares, the standard sigma trap.

3. In an induction proof that P(n) holds for all n ≥ 1, the inductive step requires you to

• (A) verify P(1), P(2) and P(3) individually
• (B) assume P(k) is true and prove P(k + 1) from it
• (C) assume P(k + 1) is true and simplify it to P(k)
• (D) prove P(n) for one very large value of n

Answer: (B). The step is an implication: *if* P(k) holds, *then* P(k + 1) holds, for an arbitrary k. (C) is the backwards-proof error; (A) and (D) are just more base cases, which never yield the general statement.

Constructed response. (a) State and verify the base case for the claim Σ_{k=1}^{n} (2k − 1) = n^2. (b) Carry out the inductive step: assume the claim for n = m and prove it for n = m + 1. (c) Use the claim to evaluate 1 + 3 + 5 + ... + 79 without adding term by term.

Scoring guide. (a) 1 point: for n = 1, LHS = 1 (the single term 2·1 − 1) and RHS = 1^2 = 1 ✓. (b) 3 points: the sum to m + 1 terms equals m^2 + (2(m + 1) − 1) = m^2 + 2m + 1 — 1 point for appending the correct (m + 1)th term using the hypothesis; factoring m^2 + 2m + 1 = (m + 1)^2 — 1 point; a concluding sentence that this is the claim with n = m + 1, completing the induction — 1 point. (c) 1 point: the last term 79 = 2n − 1 gives n = 40 terms, so the sum is 40^2 = 1600.

Going deeper: induction proves the geometric sum

Worked proof: for r ≠ 1, Σ_{k=0}^{n} ar^k = a(r^(n + 1) − 1)/(r − 1). Base (n = 0): LHS = a; RHS = a(r − 1)/(r − 1) = a ✓. Step: assume the formula for n = m. Then the sum to m + 1 terms is a(r^(m + 1) − 1)/(r − 1) + ar^(m + 1). Put over the common denominator: [a(r^(m + 1) − 1) + ar^(m + 1)(r − 1)]/(r − 1) = a[r^(m + 1) − 1 + r^(m + 2) − r^(m + 1)]/(r − 1) = a(r^(m + 2) − 1)/(r − 1) — the formula with n = m + 1. ∎ Watch the telescope inside the numerator: r^(m + 1) cancels, exactly as the finite-series derivation of Lesson 10 promised. The base case uses n = 0 here because the sum starts at k = 0 — induction starts wherever the claim starts; n_0 is part of the statement.

Bernoulli's inequality is induction's other party piece: for x > −1, (1 + x)^n ≥ 1 + nx for all n ≥ 1. Base (n = 1): equality. Step: assume (1 + x)^k ≥ 1 + kx. Multiply both sides by (1 + x) ≥ 0 (legal since x > −1 — the hypothesis earns its keep): (1 + x)^(k + 1) ≥ (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2 ≥ 1 + (k + 1)x, since kx^2 ≥ 0. ∎ This inequality bounds compound growth below by simple interest — and its proof shows induction handling inequalities with the same base-step skeleton as equalities.

Workshop: closed forms from sigma properties

Splitting a sum. Σ_{k=1}^{n} (3k − 2) = 3·Σk − Σ2 = 3n(n + 1)/2 − 2n = (3n^2 + 3n − 4n)/2 = n(3n − 1)/2. Check n = 2: the sum is 1 + 4 = 5 and the formula gives 2 × 5/2 = 5 ✓. Sigma splits over addition and pulls constants out — the two moves used here — and *only* those two: products and powers of sums do not split (Lesson 16's Σ k^2 ≠ (Σ k)^2 trap). A geometric closed form on sight: a_1 = 5, a_n = 2a_{n−1} is geometric with r = 2 in recursive clothing: a_n = 5·2^(n − 1), so a_8 = 5 × 128 = 640. Recognising standard families inside recursive definitions is the same recognition skill as the differences-and-ratios test of Lesson 19 — pattern first, formula second.