Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 37 ยท Proof Techniques

Strong Induction, Structural Induction and Recursive Definitions

Learn strong induction, structural induction on lists and trees, and recursive definitions, with proofs about primes, Fibonacci numbers and binary trees, plus Python checks.

Ordinary induction assumes only the previous case, P(k). Many arguments need more: a number splits into two smaller pieces, not just one step down. Strong induction lets you assume all earlier cases. And when the objects are not numbers but lists, trees, expressions or formulas, structural induction follows how they are built. Both are equivalent in power to ordinary induction, yet far more convenient.

Strong induction

To prove โˆ€n โ‰ฅ nโ‚€ P(n):

  1. Base case(s): prove P(nโ‚€) (and maybe a few more starting values).
  2. Strong step: for arbitrary k, assume P(j) holds for every j with nโ‚€ โ‰ค j โ‰ค k, and prove P(k + 1).

Often there is no separate base case: you prove P(n) from P(m) for all m < n, and the smallest cases are handled inside the argument ("if n is small, directly...").

Example: every integer โ‰ฅ 2 is a product of primes

Claim. Every integer n โ‰ฅ 2 is a product of one or more primes.

Proof. Let n โ‰ฅ 2 and assume the claim for all integers m with 2 โ‰ค m < n. If n is prime it is a product of one prime. Otherwise n = ab with 2 โ‰ค a, b < n. By hypothesis a and b are each products of primes, so n = ab is too. โˆŽ

Ordinary induction fails here because a and b are not n โˆ’ 1. Strong induction gives access to all smaller numbers.

Python Constructing the factorization the proof describes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Example: Fibonacci numbers

Define Fโ‚€ = 0, Fโ‚ = 1, Fโ‚™ = Fโ‚™โ‚‹โ‚ + Fโ‚™โ‚‹โ‚‚. Claim: Fโ‚™ < 2โฟ for all n โ‰ฅ 1. Two base cases are needed because the recurrence reaches back two steps: Fโ‚ = 1 < 2 and Fโ‚‚ = 1 < 4. For n โ‰ฅ 3, Fโ‚™ = Fโ‚™โ‚‹โ‚ + Fโ‚™โ‚‹โ‚‚ < 2โฟโปยน + 2โฟโปยฒ < 2โฟ. โˆŽ

Python Fibonacci facts, checked

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Recursive (inductive) definitions

Many objects are defined by building rules:

  • Lists: [] is a list; if x is an element and L a list, then x :: L is a list.
  • Binary trees: the empty tree is a tree; if L and R are trees and v a value, node(v, L, R) is a tree.
  • Propositional formulas: a variable is a formula; if A, B are formulas, so are ยฌA and A โˆง B.

Nothing else is an object of that kind (the closure clause). Functions on these objects are defined by structural recursion with one clause per building rule.

Structural induction

To prove P(x) for every object x of an inductively defined set:

  1. Base: prove P for the basic objects (empty list, empty tree, variables).
  2. Step: for each constructor, assume P for the components and prove it for the compound object.

It is strong induction on the size of the object, repackaged.

Example: a tree has one more leaf-slot than nodes

Define size(empty) = 0 and size(node(v, L, R)) = 1 + size(L) + size(R). Define slots(empty) = 1 and slots(node(v, L, R)) = slots(L) + slots(R): the number of empty positions.

Claim. slots(T) = size(T) + 1 for every binary tree T.

Base. slots(empty) = 1 = 0 + 1. โœ“ Step. Assume it for L and R. Then slots(node) = slots(L) + slots(R) = (size L + 1) + (size R + 1) = (1 + size L + size R) + 1 = size(node) + 1. โˆŽ

Python Structural recursion and induction on trees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which induction?

Ordinary Uses P(k) only
Strong Uses every smaller case
Structural Follows how objects are built
All equivalent Choose the most convenient

Match the proof to the definition

1 / 2

Induction on formulas

Chapter 2 and 3 proofs about formulas (for example that every formula has an equivalent in negation normal form, or that ev terminates) are structural inductions. For instance: every propositional formula built from variables, ยฌ and โˆง contains equally many ( and ) in its fully parenthesized form. Base: a variable has zero of each. Step for (A โˆง B): it adds one ( and one ) to the counts of A and B. For ยฌA: no parentheses are added. โˆŽ

When induction goes wrong

  • A step that needs more than you assumed. If your step uses P(k โˆ’ 1) and P(k), you need two base cases.
  • Assuming the wrong hypothesis. In strong induction you may assume P(j) only for j smaller than the current case.
  • Induction on the wrong variable. For statements with two parameters, decide which to induct on (or use induction on m + n).
  • Unfounded recursion. Structural recursion requires each recursive call to be on a smaller component, otherwise the definition may not terminate. Termination itself is proved by induction.

Common mistakes

  • Using ordinary induction where the proof needs access to non-adjacent cases.
  • Forgetting the extra base cases demanded by multi-step recurrences.
  • In structural induction, skipping one constructor.
  • Treating the closure clause ("nothing else is a tree") as optional.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Strong induction lets you assume...

    All earlier cases are available when proving P(k+1).
  2. 2. Why does the prime-factorization proof need strong induction?

    We need the hypothesis for arbitrary smaller numbers a and b.
  3. 3. A recurrence Fโ‚™ = Fโ‚™โ‚‹โ‚ + Fโ‚™โ‚‹โ‚‚ typically requires...

    The step reaches back two positions, so the first two values must be established directly.
  4. 4. In structural induction on binary trees, the step must handle...

    For node(v, L, R) assume the claim for L and R, then prove it for the whole tree.

Summary

  • Strong induction assumes all smaller cases; it is ideal when a case splits into arbitrary smaller pieces.
  • Multi-step recurrences need several base cases.
  • Inductively defined sets (lists, trees, formulas) have a base, constructors and a closure clause.
  • Structural induction proves a property by handling each constructor with its components assumed.
  • Recursion, induction and well-foundedness are three views of one idea; the next chapters build on it with sets and functions.

Next: Sets and Set Operations