Lecture 13 — Sequences and Mathematical Induction
Pre-work: Video 016 (Sequences) and Video 017 (Mathematical Induction). See sequences-and-summations for the notation and sum manipulations, and mathematical-induction for the proof template, the worked examples and the inequality rules. The worked questions are below.
Learning goals
- Gain fluency in the use of standard notation for sequences and summations.
- Understand how to apply the principle of mathematical induction to prove properties of summations and inequalities.
The first goal is about four notations: \((a_n)_{n \geq 0}\), \(\{a_n\}_{n=1}^{\infty}\), \(a_1, a_2, a_3, \dots\) and \(\sum_{n=1}^{m} a_n\).
Two questions about induction proofs
Do we have to write/know basis step, inductive hypothesis etc? It is a good idea to list these explicitly in your proofs to help the reader to follow the proof.
How does the LHS = RHS in the example from video 17? \(P(k)\) is the statement \(1 + 2 + \cdots + k = \frac{k(k+1)}{2}\), so \(P(k+1)\) is the statement \(1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\). Working from the left:
\[L.H.S = \underbrace{1 + 2 + \cdots + k}_{\text{arithmetic series}} + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2} = R.H.S\]
The step that does the work is replacing \(1 + 2 + \cdots + k\) — an arithmetic series — by the closed form the inductive hypothesis supplies.
Defining a sequence
Three ways: by an explicit formula, recursively from one or more preceding terms, or in words. Full definitions and examples in sequences-and-summations.
Sequences cannot be defined by listing their first few terms (unless you can list all of them). Asked for the next term after \(1, 4, 9, 16\): under \(a_n = n^2\) it is 25; under \(a_n = n^2 \bmod 20\) it is 5. Searching the Online Encyclopedia of Integer Sequences (https://oeis.org) for \(1, 4, 9, 16\) returns 397 possible sequences.
Working with sums
\[\sum_{i=m}^{n} a_i \pm \sum_{i=m}^{n} b_i = \sum_{i=m}^{n}(a_i \pm b_i) \qquad\qquad \sum_{i=m}^{n} c\,a_i = c\sum_{i=m}^{n} a_i\]
Worked: change of variable
(a) What expression results from applying the change of variable \(j = i+1\) to \(\displaystyle\sum_{i=0}^{n-1}(2i+5)\)?
With \(i = j - 1\):
- lower limit: \(j = 0 + 1 = 1\)
- upper limit: \(j = (n-1) + 1 = n\)
- general term: \(2i + 5 = 2(j-1) + 5 = 2j + 3\)
\[\sum_{i=0}^{n-1}(2i+5) = \sum_{j=1}^{n}(2j+3)\]
(b) Use the change of variable from part (a) to simplify \(\displaystyle 3\sum_{j=1}^{n}(j^2+2j) + \sum_{i=0}^{n-1}(2i+5)\).
Rewriting the second sum over \(j\) puts both sums on the same index range, so they can be combined termwise:
\[\sum_{j=1}^{n} 3(j^2+2j) + \sum_{j=1}^{n}(2j+3) = \sum_{j=1}^{n}\Big(3(j^2+2j) + (2j+3)\Big) = \sum_{j=1}^{n}\big(3j^2 + 8j + 3\big)\]
Q4 from the pre-class multiple choice questions
The point of the question is splitting off the last term of a sum, which is done often when proving a summation property by mathematical induction:
\[\sum_{i=1}^{n+1}(3i+2) = \underbrace{(3\cdot1+2)}_{i=1} + \underbrace{(3\cdot2+2)}_{i=2} + \cdots + \underbrace{(3n+2)}_{i=n} + \underbrace{(3(n+1)+2)}_{i=n+1} = \sum_{i=1}^{n}(3i+2) + \big(3(n+1)+2\big)\]
Worked: three rewrites of one sum
Let \(k \in \mathbb{Z}\), \(k \geq 2\). Which of the following expressions is equal to \(\displaystyle\sum_{i=1}^{k+1}(2i-1)\)?
The restriction \(k \geq 2\) matters for option C: \(\sum_{i=1}^{k-1}(2i-1) + 4k\) only has something to sum once \(k - 1 \geq 1\).
All three of A, B and C. Each is the same sum described differently:
- A. \(\displaystyle\sum_{j=0}^{k}(2j+1)\) — a change of variable, \(j = i - 1\). The limits shift from \(1 \dots k+1\) to \(0 \dots k\), and \(2i - 1 = 2(j+1) - 1 = 2j + 1\).
- B. \(\displaystyle\sum_{i=1}^{k}(2i-1) + 2k + 1\) — split off the last term, \(i = k+1\), which is \(2(k+1) - 1 = 2k + 2 - 1 = 2k+1\).
- C. \(\displaystyle\sum_{i=1}^{k-1}(2i-1) + 4k\) — split off the last two terms, \(i = k\) and \(i = k+1\), which together give \((2k-1) + (2k+1) = 4k\).
Written as sigma notation the three look like different objects. Written out as terms they are visibly one list, bracketed three ways (Figure 1). The split in B is the one worth memorising: it is the move Q4 is about — splitting off the last term — and the move every induction proof over a sum begins with.
Figure 1: One sum, three groupings — why all three options are correct. The boxed row is \(\sum_{i=1}^{k+1}(2i-1)\) written out. A keeps every term and only relabels the index (\(j = i-1\)); B brackets off the last term; C brackets off the last two and adds them, \((2k-1)+(2k+1) = 4k\). Nothing is added or removed in any of the three.
Mathematical induction
Let \(P(n)\) be a predicate in some integer \(n\). Given that (1) \(P(2)\) is true and (2) \(\forall k \in \mathbb{Z}\) with \(k \geq 2\), if \(P(k)\) then \(P(k+1)\) — then \(P(5)\) follows by applying (2) three times, and in fact \(P(n)\) is true for each integer \(n \geq 2\). The chain of modus ponens steps, and why the basis step is not optional, are in mathematical-induction.
The worked summation example — \(\displaystyle\sum_{i=1}^{n}(3i+2) = \frac{3n^2+7n}{2}\) for each integer \(n \geq 1\) — is written out there in full, with the four steps every induction proof takes: 1 define the predicate, 2 base case, 3 assume the inductive hypothesis \(P(k)\), 4 prove \(P(k+1)\).
Worked: a summation proof
Prove that for each integer \(n \geq 1\), \(\displaystyle\sum_{i=1}^{n}(2i-1) = n^2\).
Let \(P(n)\) be the predicate \(\displaystyle\sum_{i=1}^{n}(2i-1) = n^2\).
Basis step (\(n = 1\)). LHS of \(P(1)\): \(\displaystyle\sum_{i=1}^{1}(2i-1) = 2 - 1 = 1\). RHS of \(P(1)\): \(1^2 = 1\). Therefore \(P(1)\) is true.
Inductive step. Prove \(P(k) \to P(k+1)\) for all \(k \geq 1\) where \(k \in \mathbb{Z}\).
Suppose \(P(k)\) holds. Then \(\displaystyle\sum_{i=1}^{k}(2i-1) = k^2\).
LHS of \(P(k+1)\):
\[\sum_{i=1}^{k+1}(2i-1) = \sum_{i=1}^{k}(2i-1) + \big(2(k+1)-1\big) = k^2 + 2k + 1 \qquad \text{(by the inductive hypothesis } P(k)\text{)}\] \[= (k+1)^2\]
which is the RHS of \(P(k+1)\). Therefore \(P(k) \to P(k+1)\). //
Conclusion. Therefore, by the principle of mathematical induction, \(\displaystyle\sum_{i=1}^{n}(2i-1) = n^2\) for each integer \(n \geq 1\).
The // marks the end of the inductive step. The concluding sentence finishes the proof.
Mathematical induction to prove an inequality
You must be careful when manipulating inequalities — the full table of what can and cannot be concluded is in mathematical-induction. The two traps: multiplying by a negative flips the direction, and \(a < b\) together with \(x > y\) lets you conclude nothing about \(a + x\).
The example from the second video, \(n^2 < 2^n\) for each integer \(n \geq 5\), is worked through there as well.
Worked: an inequality proof
Prove that for each integer \(n \geq 2\), \(5^n + 9 < 6^n\).
Let \(P(n)\) be the predicate \(5^n + 9 < 6^n\).
Basis step (\(n = 2\)). LHS of \(P(2) = 5^2 + 9 = 25 + 9 = 34\); RHS of \(P(2) = 6^2 = 36\). Since \(34 < 36\), \(P(2)\) is true.
Inductive step. Prove \(P(k) \to P(k+1)\) for all \(k \geq 2\), \(k \in \mathbb{Z}\).
Assume \(P(k)\): \(5^k + 9 < 6^k\). The goal is \(P(k+1)\): \(5^{k+1} + 9 < 6^{k+1}\).
\[\text{LHS of } P(k+1) = 5^{k+1} + 9 = 5(5^k + 9) - 4 \times 9\] \[< 5(6^k) - 4 \times 9 \qquad \text{(by the inductive hypothesis } P(k)\text{)}\] \[< 6 \cdot 6^k - 4 \times 9 \qquad (5 < 6)\] \[< 6^{k+1} \qquad (-4 \times 9 < 0)\]
which is the RHS of \(P(k+1)\). Therefore \(P(k) \to P(k+1)\). //
Conclusion. Therefore, by the principle of mathematical induction, \(5^n + 9 < 6^n\) for each integer \(n \geq 2\).
The opening rewrite is the trick worth remembering: \(5(5^k + 9) - 4 \times 9 = 5^{k+1} + 45 - 36 = 5^{k+1} + 9\), which manufactures the exact expression \(5^k + 9\) that the inductive hypothesis bounds.
See also
- sequences-and-summations · mathematical-induction · proof-techniques
- 2026-08-20-euclidean-algorithm — Lecture 12
- practice-problems — §16 Sequences, with full worked solutions
- practice-problems — §17 Mathematical Induction, with full worked solutions