COMP233 · Chapter 5 Interactive Companion

Sequences and Mathematical Induction

Sequences, summation and product notation, factorials, and the principle of mathematical induction, the tool for proving a statement true for infinitely many integers at once. Sections 5.1–5.3.
Back to COMP233

About this chapter

A sequence is an ordered list of numbers indexed by integers, and almost every loop you will ever write walks one. Section 5.1 gives the notation, summation Σ, product Π, and factorial, and the algebra for reshaping sums. Sections 5.2 and 5.3 introduce the chapter's real subject: mathematical induction, the technique for proving a claim holds for every integer from some starting point on.

Why it matters. Induction is how we prove a closed-form sum equals its loop, that an algorithm is correct for every input size, and that a recurrence has the formula we conjectured. It is the backbone of the analysis of algorithms, and it is what justifies results you have already used, such as “a set with n elements has 2n subsets” in Chapter 6.

A note on its name. Despite the word “induction”, mathematical induction is a deductive method: it proves with certainty, not by example. We make that distinction precise in 5.3.
Recorded lecture

Mathematical Induction (Sections 5.2–5.3)

The full recorded session for sections 5.2 and 5.3. Watch it alongside this companion: the worked proofs below mirror the lecture, and the induction-proof walker and the divisibility, inequality and recurrence checkers let you practise each method as it is introduced.

Section 5.1Sequences

Definitions (Epp §5.1)
A sequence is a function from a set of consecutive integers to a set of elements; each element is a term. We write ak for the k-th term; k is the index (or subscript), and m, n are the lower and upper limits.
An explicit formula gives ak directly as an expression in k. A factor of (−1)k makes the signs alternate.

Going the other way, fitting a formula to given terms is a conjecture, not a proof: read off two patterns, the size and the sign. For 1, −1/4, 1/9, −1/16, … the sizes are 1/k2 and the signs alternate starting positive, giving ak = (−1)k+1/k2. A fitted formula should be proved (by induction, later in this chapter).

5.1.1 Sequence-term generator

Choose an explicit formula and a range; the panel lists the terms. Notice how (−1)k drives the alternating sign.

5.1.2 Summation and product notation

Definitions (Epp §5.1)
The Greek capital sigma means “add”: nΣk=m ak = am + am+1 + … + an. The capital pi means “multiply”: nΠk=m ak = am · am+1 · … · an. Read three things off the symbol: the lower limit m (where to start), the upper limit n (where to stop), and the index k (which steps up by 1).
Four moves let you reshape a sum, and each is a loop transformation: expand (write every term), fold back to Σ, separate or absorb the last term, and telescope (consecutive pieces cancel).

5.1.3 Summation / product calculator

Pick a term formula and limits; the panel expands the sum, evaluates it, and shows the closed form where one is known.

5.1.4 Telescoping

The idea
Split each term into a difference of two pieces; consecutive pieces cancel, leaving only the two ends. In general, nΣk=m (bk − bk+1) = bm − bn+1: only the first and last pieces survive. Classic example: 1/(k(k+1)) = 1/k − 1/(k+1), so nΣk=1 1/(k(k+1)) = 1 − 1/(n+1) = n/(n+1).
Watch the cancellation and the closed form for your chosen n:

5.1.5 Factorials

Definition (Epp §5.1)
n factorial is n! = n · (n−1) · … · 2 · 1, with the recursive rule n! = n · (n−1)! and base case 0! = 1. The base case 0! = 1 keeps counting and binomial formulas working cleanly. To simplify a ratio of factorials, cancel: write the larger in terms of the smaller, e.g. (n+1)!/n! = n+1.

5.1.6 Properties and change of variable

Theorem 5.1.1 (properties of summations)
For sequences ak, bk and any constant c:
Σ (ak + bk) = Σ ak + Σ bk (split / combine)  ·  Σ c·ak = c · Σ ak (pull out a constant)  ·  Π (ak bk) = (Π ak)(Π bk) (multiply termwise).

The index is a dummy variable: its name carries no meaning, so you may rename or shift it, as long as you adjust the limits to match. Shifting the index is exactly how you fix an off-by-one when re-indexing a loop.

Worked example: shifting the index by a substitution
Rewrite nΣk=3 (k − 2)2 with a new index j = k − 2.
Substitute k = j + 2. The summand (k − 2)2 becomes j2.
Fix the limits from the substitution: k = 3 ⇒ j = 1, and k = n ⇒ j = n − 2.
So nΣk=3 (k − 2)2 = n−2Σj=1 j2, the same sum with a cleaner index. The rule: change every k in the summand and recompute both limits. ■
A summation is a loop
nΣk=1 ak  ≡  s = 0; for (k = 1; k ≤ n; k++) s = s + a[k];
The index is the loop counter; the limits are the loop bounds; separating a term or changing variable is adjusting those bounds; a recursive definition (product, factorial) is an accumulator loop.

Practice exercises · Section 5.1

Recommended (Epp 4th ed., §5.1): write first terms 1–6; fit a formula to given terms 10–16; compute summations & products 18–28; expand / write in Σ–Π notation 29–32, 43–52; separate off the final term 37–39; combine into a single summation 40–42, 59–61; change of variable and factorials 53–58, 62–70. Taught solutions to a selection are in the Worked solutions section.
Exercise 5.1.A · Epp 5.1 #1
Write the first four terms of ak = k / (10 + k) for k ≥ 1.

Substitute k = 1, 2, 3, 4:

a₁ = 1/11,   a₂ = 2/12 = 1/6,   a₃ = 3/13,   a₄ = 4/14 = 2/7.

Exercise 5.1.B · Epp 5.1 #11 (fit a formula)
Find an explicit formula for the sequence 0, 1, −2, 3, −4, 5, … (terms indexed from n = 1).

Two patterns. Size: the magnitudes are 0, 1, 2, 3, 4, 5, i.e. n − 1. Sign: term n = 1 is +, term n = 2 is +… check parities: a₂ = +1, a₃ = −2, a₄ = +3, so the sign is + on even n and − on odd n, i.e. (−1)n.

Combine: an = (−1)n(n − 1). Check: a₁ = (−1)(0) = 0, a₂ = (1)(1) = 1, a₃ = (−1)(2) = −2. ✓

Exercise 5.1.C · change of variable (cf. Epp 5.1 #53–58)
Re-index nΣk=2 1/(k − 1) using the substitution j = k − 1. State the new summand and both limits.

Substitute k = j + 1. The summand 1/(k − 1) becomes 1/j.

Recompute the limits: k = 2 ⇒ j = 1 and k = n ⇒ j = n − 1. Hence nΣk=2 1/(k−1) = n−1Σj=1 1/j. Same value; lower the start and the summand together.

Section 5.2Mathematical induction I

Some claims are about infinitely many integers at once: “every amount of 8 cents or more can be paid with 3-cent and 5-cent coins”, or “1 + 2 + … + n = n(n+1)/2 for every n ≥ 1”. We cannot check the cases one by one. Induction proves them all in two steps.

The principle of mathematical induction (Epp §5.2)
To prove P(n) is true for all integers n ≥ a:
1. Basis step. Prove P(a) directly.
2. Inductive step. Prove that for every k ≥ a, if P(k) is true then P(k+1) is true.
Then P(n) holds for all n ≥ a. The basis topples the first domino; the inductive step makes each falling domino topple the next.

The assumption P(k) in the inductive step is the inductive hypothesis. This is not circular: we assume P(k) for a single k and show that this forces P(k+1). We never assume the conclusion for all n; the basis plus that single link is what makes the whole chain fall.

5.2.0 How to find an induction proof: the strategy

The skeleton never changes, so the real work is the inductive step, and it is always algebra. First write P(n) explicitly, then write out P(1) (or P(a)), P(k), and P(k+1) on paper so you can see exactly what to prove. The single trick that makes the step work: make P(k) appear inside P(k+1), then substitute the hypothesis.
The move, by problem type
  • Sums. The left side of P(k+1) is the left side of P(k) plus the next term. Peel off that last term, replace the rest by the closed form (the hypothesis), then do algebra to reach P(k+1)'s right side. The term you add is always the (k+1)-th.
  • Divisibility (d | f(n)). Write the hypothesis as f(k) = d·r. In f(k+1), factor so a copy of f(k) (or of d) appears, leaving a visible multiple of d.
  • Inequalities. Start the basis at the first n where the claim actually holds. In the step, transform the k+1 side and bound the new piece using the hypothesis plus one small estimate (e.g. 2 ≤ 2k).
  • Recurrences. The recurrence is the link: substitute ak+1 = (the recurrence in ak), then apply the hypothesis.
What to look for: the part of P(k+1) that matches P(k) , that is where the hypothesis plugs in. If you never use the hypothesis, it is not an induction proof. Common slips: choosing the wrong basis, and asserting algebra instead of deriving it.

5.2.1 A first full proof: the coin problem

Proposition 5.2.1: every integer amount n ≥ 8 can be paid with 3-cent and 5-cent coins
Basis (n = 8). 8 = 3 + 5. Payable. ✓
Inductive hypothesis. Assume some amount k ≥ 8 is payable.
Inductive step. Show k + 1 is payable, in two cases on the k-cent payment:
Case 1, it uses at least one 5: replace one 5-cent coin by two 3-cent coins (−5 + 6 = +1). New total k + 1. ✓
Case 2, it uses only 3s (so at least three of them, since k ≥ 8): replace three 3-cent coins by two 5-cent coins (−9 + 10 = +1). New total k + 1. ✓
In both cases k + 1 is payable, so by induction every n ≥ 8 is payable. ■

5.2.2 Gauss and the sum of the first n integers

Theorem 5.2.2 (sum of the first n integers)
For every integer n ≥ 1:   1 + 2 + 3 + … + n = n(n+1)/2.

The young Gauss is said to have added 1 + 2 + … + 100 by pairing the ends: 1 + 100, 2 + 99, …, fifty pairs of 101, giving 5050. A closed form returns the total in one step instead of looping; induction proves the loop and the closed form always agree.

Proof by induction on n
Basis (n = 1). Left side = 1; right side = 1·2/2 = 1. Equal. ✓
Hypothesis. Assume 1 + 2 + … + k = k(k+1)/2 for some k ≥ 1.
Step. Add (k+1) to both sides:
1 + 2 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2,
which is the formula at n = k+1. So by induction it holds for all n ≥ 1. ■
Verify the loop and the closed form agree for any n:

5.2.3 The geometric sum

Theorem 5.2.3 (sum of a geometric sequence)
For a fixed ratio r ≠ 1 and integer n ≥ 0:   1 + r + r2 + … + rn = (rn+1 − 1)/(r − 1).

A geometric sum adds powers of a fixed ratio. It appears in compound interest, the cost of loop-doubling, and binary place values, and the closed form collapses the whole sum into one fraction. (Proof by induction on n: basis n = 0 gives 1 = (r−1)/(r−1); the step adds rk+1 and combines over r − 1.)

Sum powers of r and compare with the closed form:

5.2.4 Induction proof walker

Step through the basis, hypothesis, and inductive step of each standard proof.

Practice exercises · Section 5.2

Recommended (Epp 4th ed., §5.2): model a coin / postage problem 1, 2; prove a sum formula directly 6, 7, 8, 9; prove the standard formulas (Σi2, Σi3, …) 10, 11, 12, 13, 17; evaluate a sum using the theorems 20, 21, 22, 23, 25, 26. Taught solutions are in the Worked solutions section.
Exercise 5.2.A · Epp 5.2 #6
Prove by induction, without using Theorem 5.2.2: for all integers n ≥ 1, 2 + 4 + 6 + … + 2n = n2 + n.

Basis (n = 1). Left = 2; right = 1 + 1 = 2. ✓

Hypothesis. Assume 2 + 4 + … + 2k = k2 + k for some k ≥ 1.

Step. Add the next term 2(k+1):

2 + 4 + … + 2k + 2(k+1) = (k2 + k) + 2(k+1) = k2 + 3k + 2 = (k+1)2 + (k+1).

That is the formula at n = k+1, so it holds for all n ≥ 1. ■

Exercise 5.2.B · evaluate a geometric sum (cf. Epp 5.2 #20–26)
Use the geometric-sum formula to write nΣk=0 3k in closed form, then compute 5Σk=1 3k.

By Theorem 5.2.3 with r = 3: nΣk=0 3k = (3n+1 − 1)/(3 − 1) = (3n+1 − 1)/2.

For k = 1 to 5, drop the k = 0 term (which is 1): (36 − 1)/2 − 1 = 728/2 − 1 = 364 − 1 = 363. Check: 3 + 9 + 27 + 81 + 243 = 363. ✓

Section 5.3Mathematical induction II

The same recipe, basis then inductive step, proves three further families of statement: divisibility, inequalities, and closed forms of recursive sequences. Only the algebra of the step changes.

5.3.1 Divisibility by induction

Method
“d divides x” means x = d · (some integer). In the step, write the hypothesis multiple explicitly (e.g. = 3r), then peel the next case down to a multiple of d.
Proposition 5.3.1: 22n − 1 is divisible by 3, for all integers n ≥ 0
Basis (n = 0). 20 − 1 = 0 = 3 · 0. Divisible by 3. ✓
Hypothesis. Assume 22k − 1 = 3r for some integer r, i.e. 22k = 3r + 1.
Step. 22(k+1) − 1 = 4 · 22k − 1 = 4(3r + 1) − 1 = 12r + 3 = 3(4r + 1).
Since 4r + 1 is an integer, 22(k+1) − 1 is divisible by 3. By induction the claim holds for all n ≥ 0. ■
Check the value and its quotient by 3 for any n:

5.3.2 Inequalities by induction

Method
Start the basis at the first value where the claim actually holds (often not n = 1). In the step, transform the k+1 side and bound it using the hypothesis plus a small extra estimate.
Proposition 5.3.2: 2n + 1 < 2n, for all integers n ≥ 3
Basis (n = 3). 2·3 + 1 = 7 < 8 = 23. ✓ (It fails at n = 2: 5 < 4 is false, which is why the basis is 3.)
Hypothesis. Assume 2k + 1 < 2k for some k ≥ 3.
Step. 2(k+1) + 1 = (2k + 1) + 2 < 2k + 2 ≤ 2k + 2k = 2k+1,
using the hypothesis and 2 ≤ 2k for k ≥ 3. So the claim holds for all n ≥ 3. ■
Compare 2n + 1 with 2n; note where the inequality first holds:

5.3.3 Closed form of a recursive sequence

Method
A sequence given by a recurrence can be proved equal to a conjectured closed form by induction: the recurrence supplies the link the inductive step needs.
Example: a₁ = 3, ak = 7ak−1 for k ≥ 2. Claim: an = 3 · 7n−1 for all n ≥ 1 (Epp 5.3.24)
Basis (n = 1). a₁ = 3; formula gives 3 · 70 = 3. ✓
Hypothesis. Assume ak = 3 · 7k−1 for some k ≥ 1.
Step. By the recurrence, ak+1 = 7ak = 7 · 3 · 7k−1 = 3 · 7k = 3 · 7(k+1)−1. ✓
So the closed form holds for all n ≥ 1. ■
Compute the term by the recurrence and by the closed form, and confirm they agree:

5.3.4 Inductive vs deductive reasoning

Inductive reasoning
Starts from observations and examples; moves from specific to general; produces a conjecture, it suggests but does not prove.
Deductive reasoning
Starts from definitions and theorems; moves from general to specific; produces a proof, the conclusion is guaranteed.

Despite the shared word, mathematical induction is a deductive method: the basis and inductive step together prove the statement with certainty for every n ≥ a. The pattern-spotting that suggests a formula is inductive reasoning; the induction proof that confirms it is deductive.

Practice exercises · Section 5.3

Recommended (Epp 4th ed., §5.3): divisibility by induction 8, 9, 10, 11, 12, 14, 15; inequalities by induction 16, 17, 18, 19, 20, 23; closed form of a recursive sequence 24, 25, 26, 27. Taught solutions are in the Worked solutions section.
Exercise 5.3.A · Epp 5.3 #9
Prove by induction: 7n − 1 is divisible by 6, for every integer n ≥ 0.

Basis (n = 0). 70 − 1 = 0 = 6 · 0. ✓

Hypothesis. Assume 7k − 1 = 6r for some integer r, i.e. 7k = 6r + 1.

Step. 7k+1 − 1 = 7 · 7k − 1 = 7(6r + 1) − 1 = 42r + 6 = 6(7r + 1). Since 7r + 1 is an integer, 7k+1 − 1 is divisible by 6. By induction, true for all n ≥ 0. ■

WorkedTaught solutions to recommended exercises

A selection of the exercises recommended on the slides, solved in full and grounded in Epp's exercise sets. Attempt each on paper before revealing.

W1 · Epp 5.1 #3 (alternating terms)
Write the first four terms of ci = (−1)i / 3i for i ≥ 0.

Substitute i = 0, 1, 2, 3; the (−1)i flips the sign each step:

c₀ = 1/1 = 1,   c₁ = −1/3,   c₂ = 1/9,   c₃ = −1/27.

W2 · Epp 5.1, telescoping (cf. #18–28, 40–42)
Evaluate nΣk=1 1/(k(k+1)) in closed form.

Split by partial fractions: 1/(k(k+1)) = 1/k − 1/(k+1). The sum telescopes:

(1 − 1/2) + (1/2 − 1/3) + … + (1/n − 1/(n+1)) = 1 − 1/(n+1) = n/(n+1).

Every interior piece cancels with its neighbour, leaving only the first piece 1 and the last −1/(n+1).

W3 · Epp 5.1, factorials (cf. #62–70)
Simplify (n + 2)! / n! for an integer n ≥ 0.

Write the larger factorial in terms of the smaller, then cancel:

(n + 2)! / n! = [(n + 2)(n + 1) · n!] / n! = (n + 2)(n + 1) = n2 + 3n + 2.

W4 · Epp 5.2 #1 (model on the coin proof)
Show by induction that any amount of at least 14 cents can be made with 3-cent and 8-cent coins.

Basis (n = 14). 14 = 3 + 3 + 8. Payable. ✓

Hypothesis. Assume some amount k ≥ 14 is payable with 3s and 8s.

Step. Show k + 1 is payable, in two cases on the k-cent payment:

  • Case 1, it uses at least one 8: replace one 8 by three 3s (−8 + 9 = +1), giving k + 1.
  • Case 2, it uses only 3s: since k ≥ 14, there are at least five 3s; replace five 3s by two 8s (−15 + 16 = +1), giving k + 1.

In both cases k + 1 is payable, so by induction every n ≥ 14 is payable. ■

W5 · Epp 5.2 #10 (a standard formula)
Prove by induction: for all integers n ≥ 1, 12 + 22 + … + n2 = n(n+1)(2n+1)/6.

Basis (n = 1). Left = 1; right = 1·2·3/6 = 1. ✓

Hypothesis. Assume 12 + … + k2 = k(k+1)(2k+1)/6.

Step. Add (k+1)2:

k(k+1)(2k+1)/6 + (k+1)2 = (k+1)[k(2k+1) + 6(k+1)]/6 = (k+1)(2k2 + 7k + 6)/6.

Factor: 2k2 + 7k + 6 = (k+2)(2k+3), so the sum is (k+1)(k+2)(2k+3)/6, which is the formula at n = k+1 (since 2(k+1)+1 = 2k+3). ■

W6 · Epp 5.2 #20 (evaluate using the theorem)
Evaluate 4 + 8 + 12 + 16 + … + 200.

Factor out the common 4: 4 + 8 + … + 200 = 4(1 + 2 + … + 50).

By Theorem 5.2.2, 1 + 2 + … + 50 = 50·51/2 = 1275.

So the sum is 4 · 1275 = 5100.

W7 · Epp 5.3 #19 (inequality)
Prove by induction: n2 < 2n for all integers n ≥ 5.

Basis (n = 5). 25 < 32. ✓ (It fails at n = 2, 3, 4, so the basis is 5.)

Hypothesis. Assume k2 < 2k for some k ≥ 5.

Step. (k+1)2 = k2 + 2k + 1. For k ≥ 5, 2k + 1 < k2 (since k2 − 2k − 1 = (k−1)2 − 2 > 0). So

(k+1)2 = k2 + (2k + 1) < k2 + k2 = 2k2 < 2 · 2k = 2k+1.

So the claim holds for all n ≥ 5. ■

W8 · Epp 5.3 #25 (recursive sequence inequality)
A sequence is defined by b0 = 5 and bk = 4 + bk−1 for k ≥ 1. Show bn > 4n for all integers n ≥ 0.

Basis (n = 0). b0 = 5 > 0 = 4·0. ✓

Hypothesis. Assume bk > 4k for some k ≥ 0.

Step. By the recurrence, bk+1 = 4 + bk > 4 + 4k = 4(k+1), using the hypothesis. So bk+1 > 4(k+1), and by induction bn > 4n for all n ≥ 0. ■

W9 · Epp 5.1, factorial simplification (cf. #62–70)
Using the recursive definition of factorial, simplify (2n + 1)! / (2n − 1)! completely (no factorial notation), for an integer n ≥ 1.

Expand the larger factorial just far enough to reach the smaller one, using m! = m · (m−1)! twice:

(2n + 1)! = (2n + 1) · (2n)! = (2n + 1) · (2n) · (2n − 1)!

So (2n + 1)! / (2n − 1)! = (2n + 1)(2n) = 4n2 + 2n. The (2n − 1)! cancels entirely, leaving a polynomial.

W10 · Epp 5.1, telescoping a difference (cf. #18–28)
Evaluate nΣk=1 (√(k+1) − √k) in closed form.

This is already in difference form bk − bk+1 with bk = √k (written as √(k+1) − √k = −(bk − bk+1)), so it telescopes:

(√2 − √1) + (√3 − √2) + … + (√(n+1) − √n) = √(n+1) − 1.

Every interior √ appears once with each sign and cancels; only √(n+1) and −√1 = −1 survive. So the sum is √(n+1) − 1.

Recap: Chapter 5

  • A sequence is an ordered list of terms indexed by integers; an explicit formula gives the k-th term directly. Fitting a formula to terms is a conjecture, to be proved by induction.
  • Σ adds terms and Π multiplies them; reshape sums by expanding, separating or absorbing a term, changing the index, and telescoping. The factorial n! is the key product, with 0! = 1; simplify ratios by cancelling.
  • Mathematical induction proves P(n) for all n ≥ a via a basis step and an inductive step P(k) → P(k+1). The inductive hypothesis is assumed for one k; this is not circular.
  • Two formulas to know: the sum of the first n integers n(n+1)/2, and the geometric sum (rn+1 − 1)/(r − 1).
  • The same method proves divisibility (write “divisible by d” as d × an integer), inequalities (start the basis where the claim first holds), and the closed form of a recurrence (the recurrence supplies the inductive link).
  • Despite its name, mathematical induction is a deductive method: it proves with certainty for every n.
Where it leads. Induction underpins the 2n subset count of Chapter 6, the analysis of recursive algorithms, and the correctness proofs you will meet throughout computer science.