MA2011 / MA2211 · Week 7

Sequences &
Mathematical Induction

7.1 Sequences & Recursion · 7.2 Mathematical Induction

Discrete Mathematics for Computing · James Cook University

Recap · Week 6

Where we left off

6.1 Functions

Abstract functions, composition, identity & inverses.

6.2 Relations

Reflexive, symmetric, antisymmetric, transitive. Matrices & digraphs.

6.3 Equivalence & Order

Equivalence classes, partitions. Order relations.

Bridge to today

A sequence is simply a function a : ℕ → ℝ — the same functions you studied in Week 6, but now the input is always a natural number (an index), and the output is the n-th term.

Today we also learn mathematical induction — the main proof tool for statements about all natural numbers.

Section 7.1

Sequences
& Recursion

Let's start with something concrete — before any formal definition, let's just list some numbers.

7.1 · Sequences

Step 1 — just look at some lists

Which of these look like a pattern you could continue?

List	Next term?	Pattern?
2, 4, 6, 8, 10, …	12	Add 2 each time
1, 3, 9, 27, 81, …	243	Multiply by 3 each time
1, 1, 2, 3, 5, 8, 13, …	21	Sum of previous two
1, 4, 9, 16, 25, …	36	Perfect squares

💭 Pause & Think

Each list has a rule that generates the next number. A sequence is just an infinite list generated by such a rule.

We label each position with an index: the 1st term is a₁, the 2nd is a₂, and so on.

7.1 · Sequences

Reading sequence notation

Take the even numbers: 2, 4, 6, 8, 10, …

2

a₁

→

4

a₂

→

6

a₃

→

8

a₄

→

10

a₅

…

What we write

a_n = 2n (for n = 1, 2, 3, …)

The subscript n is the index (position). The value a_n is the n-th term.

Let's verify by plugging in

n	a_n = 2n	Value
1	2 × 1	2 ✔
2	2 × 2	4 ✔
3	2 × 3	6 ✔
100	2 × 100	200

✔ We can find the 100th term instantly — no counting!

7.1 · Sequences

Two ways to describe the same sequence

Let's use: 3, 7, 11, 15, 19, … (add 4 each time, starting at 3)

🚀 Closed form (direct formula)

a_n = 4n − 1 (n ≥ 1)

Verification

n	4n − 1
1	4(1)−1 = 3	✔
2	4(2)−1 = 7	✔
3	4(3)−1 = 11	✔

Advantage: Jump straight to any term. a₅₀ = 4(50)−1 = 199.

🔄 Recursive (step by step)

a₁ = 3
a_n = a_n−1 + 4 (n ≥ 2)

Trace

Step	Calculation	Value
a₁	given	3
a₂	3 + 4	7
a₃	7 + 4	11

Advantage: Makes the rule crystal clear — add 4 each time.

7.1 · Sequences

Tracing a recursive sequence — step by step

Let's trace through together. Sequence: a₁ = 1, a_n = 2 × a_n−1

Rule: each term is double the previous term.

n	Calculation	Value a_n	What we just did
1	given	1	Base case — start here
2	2 × a₁ = 2 × 1	2	Apply rule once
3	2 × a₂ = 2 × 2	4	Apply rule again
4	2 × a₃ = 2 × 4	8	Apply rule again
5	2 × a₄ = 2 × 8	16	Apply rule again

💭 Notice the pattern?

1, 2, 4, 8, 16, … — these are powers of 2!

Can you guess the closed form? → a_n = 2ⁿ⁻¹

Key observation

To use the recursive rule, you must know the previous term. You can't find a₁₀₀ without computing all 99 terms before it — that's why a closed form is so valuable.

7.1 · Sequences

The formal definition (now that we understand the idea)

Definition

A sequence is a function a : ℕ → ℝ. We write a_n (or a(n)) for the value at index n.

Closed-form examples

a_n	First terms
2n	2, 4, 6, 8, …
n²	1, 4, 9, 16, …
3ⁿ	3, 9, 27, 81, …
2n−1	1, 3, 5, 7, …

Recursive examples

Arithmetic:
a₁=5, a_n=a_n−1+3
→ 5, 8, 11, 14, …

Geometric:
a₁=2, a_n=5·a_n−1
→ 2, 10, 50, 250, …

⚠ Watch out: domain matters!

Does n start at 0 or 1?

a_n = 2n−1, n≥1 → 1, 3, 5, …

a_n = 2n−1, n≥0 → −1, 1, 3, …

Always state where n starts!

7.1 · Sequences

Fibonacci — a sequence that needs two base cases

Imagine: each new rabbit pair = all pairs from two months ago + all pairs from last month.

Fibonacci (recursive)

F₁ = 1, F₂ = 1, F_n = F_n−1 + F_n−2 (n ≥ 3)

Let's build it together, one step at a time:

n	Calculation	F_n
1	given	1
2	given	1
3	F₂ + F₁ = 1 + 1	2
4	F₃ + F₂ = 2 + 1	3
5	F₄ + F₃ = 3 + 2	5
6	F₅ + F₄ = 5 + 3	8
7	F₆ + F₅ = 8 + 5	13

Why two base cases?

Because F_n needs the two terms before it. Without both F₁ and F₂, we can't start the chain. Try to compute F₃ with only F₁ — you can't!

7.1 · Quick Check

Sequences — test yourself

Q1 Given a₁=5, a_n=a_n−1+3 for n≥2. What is a₄?

Q2 Which is a closed-form definition?

Q3 Fibonacci: F₁=1, F₂=1, F_n=F_n−1+F_n−2. What is F₆?

Section 7.2

Mathematical
Induction

The proof technique for statements that hold for all natural numbers. We start with the intuition — no symbols yet.

7.2 · Mathematical Induction

The problem: we need to prove infinitely many things

Imagine someone claims: "The sum 1+2+3+…+n always equals n(n+1)/2."

We can check small cases…

n	Actual sum	n(n+1)/2
1	1	1	✔
2	1+2=3	3	✔
3	1+2+3=6	6	✔
4	1+2+3+4=10	10	✔
5	1+…+5=15	15	✔

⚠ But this is NOT a proof!

There are infinitely many natural numbers. Checking 5 cases (or even 5 million) tells us nothing about n = 1,000,000 or n = 10¹⁰⁰.

🆕 The Domino Analogy

Line up infinitely many dominoes. If:

The first one falls, and
Each fallen domino knocks the next one,

then all dominoes fall — even the millionth!

7.2 · Mathematical Induction

The idea in plain English — before the symbols

We want to prove: "Statement P(n) is true for every natural number n."

Two things to prove

Step 1 Base case

Show that P(1) is true.

(Push the first domino.)

Step 2 Inductive step

Show: if P(k) is true, then P(k+1) must also be true.

(Each domino knocks the next.)

💭 Why does this work?

Step 1 gives us P(1). Step 2 (applied to k=1) gives P(2). Step 2 again (k=2) gives P(3). Step 2 again (k=3) gives P(4). We can reach any n. This is the power of induction.

The key assumption in Step 2 — the "Induction Hypothesis"

In Step 2, when we say "assume P(k) is true" — that assumption is called the Induction Hypothesis (IH). We then use it to derive that P(k+1) must also be true.

7.2 · Mathematical Induction

The proof template — your recipe

Principle of Mathematical Induction

If (1) P(1) is true, and (2) for all k≥1, P(k) ⇒ P(k+1), then P(n) is true for all n≥1.

Every induction proof follows the same 5-step structure:

State

Say clearly what P(n) is. "Let P(n) be the statement: …"

Base case

Verify P(1) is true by direct calculation.

IH

"Assume P(k) is true for some arbitrary k≥1." Write out what P(k) says explicitly.

Inductive step

Using the IH, prove P(k+1) is true. This is the main calculation.

Conclude

"By induction, P(n) holds for all n≥1." □

⚠ Common mistake

Never assume what you're trying to prove! In the inductive step, you assume P(k) (about k), and prove P(k+1) (about k+1). These are different statements.

7.2 · Worked Example

Let's write the proof — setting up first

Theorem: For all n≥1, 1 + 2 + 3 + ··· + n = n(n+1)/2.

State

Let P(n) be: “1+2+…+n = n(n+1)/2.”

Base n=1

LHS = 1. RHS = 1×2/2 = 1. ✔

IH

Assume for some k≥1:
1+2+…+k = k(k+1)/2

Goal

We want to show:
1+2+…+k+(k+1) = (k+1)(k+2)/2

💭 Before the algebra — think about it

The IH tells us the sum of the first k terms. We need the sum of the first k+1 terms.

The difference is just one extra term: (k+1).

So:
(sum to k+1) = (sum to k) + (k+1)
= k(k+1)/2 + (k+1)
← this is where we use the IH!

7.2 · Worked Example

Completing the proof — the algebra

We have (from IH): 1+2+…+k = k(k+1)/2

We want: 1+2+…+k+(k+1) = (k+1)(k+2)/2

1 + 2 + … + k + (k+1)
= [1 + 2 + … + k] + (k+1)
= k(k+1)/2 + (k+1)     ← applied the IH here
= (k+1) × [k/2 + 1]     ← factor out (k+1)
= (k+1) × (k+2)/2
= (k+1)(k+2)/2     ✔

Conclude

By the principle of induction, 1+2+…+n = n(n+1)/2 for all n≥1. □

The key trick in this proof

We wrote the sum of k+1 terms as (sum of k terms) + one extra term, then applied the IH. This pattern — split off the last term, apply IH — works in almost every induction proof on sums.

7.2 · Worked Example

Divisibility by induction

Theorem: For all n≥0, 3 divides (n³ − n).

Check a few cases first

n	n³−n	Divisible by 3?
0	0	Yes (0 = 3×0) ✔
1	0	Yes (0 = 3×0) ✔
2	6	Yes (6 = 3×2) ✔
3	24	Yes (24 = 3×8) ✔

Looks true — but we need a proof for ALL n.

Base n=0

0³−0 = 0 = 3×0. ✔

IH

Assume 3|(k³−k), so k³−k = 3m for some integer m.

Step

(k+1)³−(k+1)
= k³+3k²+3k+1−k−1
= (k³−k) + 3k²+3k
= 3m + 3(k²+k) ← IH
= 3(m+k²+k) ✔

Conclude

By induction, 3|(n³−n) for all n≥0. □

7.2 · Strong Induction

Strong induction — when ordinary induction isn't enough

Problem: Fibonacci needs the two previous terms — ordinary IH only gives you one. What do we do?

Ordinary induction (weak)

IH: Assume P(k) is true.

You only get P(k) — the single previous case.

Strong induction

IH: Assume P(1), P(2), …, P(k) are ALL true.

You get every previous case — use whichever you need.

Example: Prove F_n < 2ⁿ for all n≥1

Base cases (n=1,2):
F₁=1 < 2¹=2 ✔
F₂=1 < 2²=4 ✔

IH (strong): Assume F_j < 2^j for all j ≤ k.

Step:

F_k+1 = F_k + F_k−1
< 2^k + 2^k−1 (IH, twice)
< 2^k + 2^k = 2^k+1 ✔

We used the IH for both F_k and F_k−1.

7.2 · Quick Check

Induction — test yourself

Q4 In a proof by induction, the Induction Hypothesis is:

Q5 Using the formula 1+2+…+n = n(n+1)/2, what is 1+2+…+10?

Q6 Why do Fibonacci proofs often need strong induction?

Section 7.A · Extra Topic

Loop
Invariants

Induction isn't just for pure mathematics — it's the rigorous way to prove your code is correct.

7.A · Loop Invariants

What stays true every time around the loop?

Consider a loop that adds up 1+2+…+n:

s = 0
i = 1
while i <= n:
    s = s + i
    i = i + 1
# goal: s == n*(n+1)/2

💭 Before the loop — trace it for n=4

i	s after step
1	0+1=1
2	1+2=3
3	3+3=6
4	6+4=10 = 4×5/2 ✔

Loop Invariant I(k)

After k iterations of the loop, s = k(k+1)/2.

Induction proof of the invariant

Base (k=0): Before loop, s=0=0×1/2. ✔
IH: After k steps, s=k(k+1)/2.
Step: At step k+1, s_new = s+{k+1} = k(k+1)/2+(k+1) = (k+1)(k+2)/2. ✔
Done: At termination k=n, so s=n(n+1)/2. ✔

Section 7.B · Extra Topic

Linear
Recurrence

A systematic way to find a closed-form formula from a recursive definition — including deriving Fibonacci's golden ratio formula.

7.B · Linear Recurrence

Finding a closed form from a recurrence

Suppose we have: a₀=1, a_n=3a_n−1

Trace first

n	a_n
0	1
1	3
2	9
3	27 = 3³

Clearly: a_n = 3ⁿ. The trick: try a_n = rⁿ.

Method for 2nd-order recurrences

For a_n = c₁a_n−1 + c₂a_n−2:

Try a_n=rⁿ → characteristic equation: r²−c₁r−c₂=0
Solve for roots r₁, r₂.
General form: a_n=Ar₁ⁿ+Br₂ⁿ
Use base cases to find A and B.

Fibonacci: r²−r−1=0

r = (1±√5)/2
φ≈1.618, ψ≈−0.618
F_n = (φⁿ−ψⁿ)/√5

This gives exact integers despite the √5!

Week 7 · Summary

What you should now be able to do

7.1 Sequences

Read and compute terms using a_n notation
Distinguish closed-form from recursive
Trace recursive sequences step by step
Recognise arithmetic, geometric, Fibonacci
Always state the domain (where n starts)

7.2 Induction

Explain why checking cases isn't a proof
Write all 5 steps: State, Base, IH, Step, Conclude
Apply the "split off last term" trick for sums
Know when to use strong induction (2+ previous terms needed)

Extra (Optional)

7.A Loop invariants
Prove correctness of while loops using induction on the iteration count.

7.B Linear recurrence
Convert recursive definitions to closed forms via characteristic equations.

Next week — Combinatorics

Counting: product rule, permutations, combinations, binomial theorem.

Problem Sheet 3

Covers Weeks 5–7. Induction proofs take practice — start early! Optional questions on 7.A and 7.B are good project material.

Sequences &Mathematical Induction

Where we left off

Step 1 — just look at some lists

Reading sequence notation

Two ways to describe the same sequence

Tracing a recursive sequence — step by step

The formal definition (now that we understand the idea)

Fibonacci — a sequence that needs two base cases

Sequences — test yourself

The problem: we need to prove infinitely many things

The idea in plain English — before the symbols

The proof template — your recipe

Let's write the proof — setting up first

Completing the proof — the algebra

Divisibility by induction

Strong induction — when ordinary induction isn't enough

Induction — test yourself

What stays true every time around the loop?

Finding a closed form from a recurrence

What you should now be able to do

Sequences &
Mathematical Induction