SEM 6 › Discrete Mathematics › Week 07
Discrete Mathematics · Week 07

Mathematical Induction & Recursion

The principle of mathematical induction (basis step, inductive step, inductive hypothesis), four fully worked proofs, the well-ordering property, and recursively defined sequences and functions (factorial, powers, sums, Fibonacci).

ITE38221 video · 39 min📄 Lesson 7- Induction Recursion.pdf

1Why induction?

Many statements claim a property holds for all positive integers n. For example:

  • 1 + 2 + … + n = n(n + 1)/2
  • n³ − n is divisible by 3
  • 4ⁿ⁺¹ > (n + 2)²

You can't check infinitely many cases one by one. Mathematical induction proves them all at once.

Principle of mathematical induction

To prove P(n) for all positive integers n:

  1. Basis step: verify that P(1) is true.
  2. Inductive step: show that P(k) → P(k + 1) is true for all positive integers k.
Remark 1 — the inductive hypothesis

In the inductive step you assume P(k) is true for an arbitrary k. This assumption is the inductive hypothesis. Then you show that P(k + 1) also holds.

Why it works:

  • P(1) is true (basis step).
  • P(1) ⇒ P(2), so P(2) is true.
  • P(2) ⇒ P(3), so P(3) is true.
  • … and so on, so P(n) is true for every n.

The domino picture

Line up infinitely many dominoes, numbered 1, 2, 3, …. Let P(n) = "domino n falls".

  • Basis: you knock over domino 1, so P(1) is true.
  • Inductive step: whenever domino k falls, it knocks over domino k + 1, so P(k) → P(k + 1).

Therefore every domino falls.

🧪 Try it — Domino induction

2Worked induction proofs

Example 7.1.1 — 1 + 2 + ⋯ + n = n(n + 1)/2

Let P(n): "the sum of the first n positive integers is n(n + 1)/2".

Basis step: 1 = 1·(1 + 1)/2, so P(1) is true.

Inductive step: - Assume P(k): 1 + 2 + ⋯ + k = k(k + 1)/2. (This is the inductive hypothesis.) - We must show P(k + 1): 1 + 2 + ⋯ + k + (k + 1) = (k + 1)(k + 2)/2. - Add (k + 1) to both sides of P(k):

1 + 2 + ⋯ + k + (k + 1) = k(k + 1)/2 + (k + 1) = [k(k + 1) + 2(k + 1)]/2 = (k + 1)(k + 2)/2 ✓

So P(k + 1) holds. By induction, P(n) is true for all positive integers n. ∎

Example 7.1.2 — 1 + 3 + 5 + ⋯ + (2n − 1) = n²

Let P(n): "the sum of the first n odd integers is n²".

Basis step: 1 = 1², so P(1) is true.

Inductive step: - Assume 1 + 3 + ⋯ + (2k − 1) = k². - Show the sum up to (2k + 1) equals (k + 1)². - Add (2k + 1), the next odd number, to both sides:

1 + 3 + ⋯ + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)² ✓ ∎

Example 7.1.3 — n < 2ⁿ (an inequality)

Basis step: 1 < 2¹ = 2, so P(1) is true.

Inductive step: - Assume k < 2ᵏ. - Show k + 1 < 2ᵏ⁺¹. - Add 1 to both sides of the hypothesis, and use 1 ≤ 2ᵏ:

k + 1 < 2ᵏ + 1 ≤ 2ᵏ + 2ᵏ = 2·2ᵏ = 2ᵏ⁺¹ ✓ ∎

Example 7.1.4 — n³ − n is divisible by 3 (a divisibility proof)

Basis step: 1³ − 1 = 0, and 3 | 0, so P(1) is true.

Inductive step: - Assume 3 | (k³ − k). - Show 3 | ((k + 1)³ − (k + 1)). - Expand and regroup:

(k + 1)³ − (k + 1) = (k³ + 3k² + 3k + 1) − (k + 1) = (k³ − k) + 3(k² + k)

The first bracket is divisible by 3 (by the hypothesis). The second is 3 times an integer. So their sum is divisible by 3 ✓ ∎

The universal recipe
  1. Define P(n) clearly.
  2. Basis: substitute n = 1 (or the given start value) and check both sides.
  3. Write the hypothesis P(k) and the target P(k + 1) explicitly.
  4. Start from P(k + 1), find P(k) inside it, and use the hypothesis. For sums, peel off the last term. For divisibility, regroup into "hypothesis part + multiple of m".
  5. Conclude: "by the principle of mathematical induction, P(n) holds for all n."
🧪 Try it — Check a formula numerically

3The well-ordering property

Well-ordering property

Every non-empty set of non-negative integers has a least element. For each such set A there is some a ∈ A with a ≤ x for all x ∈ A.

The well-ordering principle is equivalent to the principle of mathematical induction.

Examples 7.1.5 and 7.1.6
  • A = {3, 11, 5, 9, 2, 8, 16, 21} has least element 2.
  • A = {n ∈ ℕ : n > 7} is infinite, but it still has a least element: 8.

4Recursion

Sometimes it's hard to define an object explicitly, but easy to define it in terms of itself. This is recursion. It can define sequences, functions and sets.

Recursively defined sequence

  • Basis step: give the initial term a₀.
  • Recursive step: give a rule for each term in terms of the preceding term(s).

Recursively defined function (domain = non-negative integers)

  • Basis step: give the value at zero.
  • Recursive step: give a rule for the value at an integer from its values at smaller integers.
Example 7.2.1 — powers of 3

The explicit formula is aₙ = 3ⁿ. Recursively: a₀ = 1, aₙ₊₁ = 3aₙ for n = 0, 1, 2, …

Example 7.2.2 — f(0) = 3, f(n + 1) = 2f(n) + 3
  • f(1) = 2·3 + 3 = 9
  • f(2) = 2·9 + 3 = 21
  • f(3) = 2·21 + 3 = 45
  • f(4) = 2·45 + 3 = 93
Example 7.2.3 — factorial F(n) = n!

Since (n + 1)! = (n + 1)·n!:

  • F(0) = 1
  • F(n + 1) = (n + 1)·F(n)
Example 7.2.4 — powers aⁿ (a ≠ 0, n ≥ 0)
  • a⁰ = 1
  • aⁿ⁺¹ = a·aⁿ
Example 7.2.5 — sum of the first n terms
  • Basis: Σk=00 aₖ = a₀
  • Recursive: Σk=0n+1 aₖ = (Σk=0n aₖ) + aₙ₊₁
Fibonacci numbers
  • f₀ = 0, f₁ = 1
  • fₙ = fₙ₋₁ + fₙ₋₂ for n = 2, 3, 4, …

Working forward: - f₂ = 1 + 0 = 1 - f₃ = 1 + 1 = 2 - f₄ = 2 + 1 = 3 - f₅ = 3 + 2 = 5 - f₆ = 5 + 3 = 8

It needs two initial values because each term uses the two before it.

Remark 2

Recursively defined functions are well defined: the value at every positive integer is determined unambiguously. This follows from the principle of mathematical induction.

🧪 Try it — Recursion evaluator
Exam focus

Expect:

  • A full induction proof (sum formula, inequality or divisibility). Marks go to: clearly defining P(n), the basis step, stating the inductive hypothesis, the inductive step, and the conclusion.
  • "State the well-ordering property and find the least element of a set."
  • "Give a recursive definition of aₙ = 6n / 2n + 1 / 5 / 4n − 2", e.g. 6n: a₁ = 6, aₙ₊₁ = aₙ + 6.
  • "Find f(1)…f(5) given a recursive rule."

5Quick revision sheet

Concept Remember it as
Induction Basis P(1) + inductive step P(k) → P(k + 1)
Inductive hypothesis Assume P(k) for arbitrary k
Domino First falls + each knocks the next = all fall
Sum proofs Add the next term to both sides of P(k)
Divisibility proofs Regroup into (hypothesis part) + m·(integer)
Inequality proofs Add to both sides, then bound (1 ≤ 2ᵏ)
Well-ordering Every non-empty set of non-negative integers has a least element; equivalent to induction
Recursive definition Basis (initial value) + recursive rule
Factorial F(0) = 1, F(n+1) = (n+1)F(n)
Powers a⁰ = 1, aⁿ⁺¹ = a·aⁿ
Fibonacci f₀ = 0, f₁ = 1, fₙ = fₙ₋₁ + fₙ₋₂ → 0, 1, 1, 2, 3, 5, 8
f(0)=3, f(n+1)=2f(n)+3 9, 21, 45, 93

?Self-check quiz

12 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousNumber Theory & CryptographyNext →Counting — Product & Sum Rules, Permutations & Combinations