Course contentsShow
← Computer Science
Lesson 94 of 2,8722. Discrete Mathematics for CSFree lesson

Structural Induction

Applying induction to recursively defined structures like trees, lists, and formal expressions.

Structural Induction

What You'll Learn

You'll learn how to prove properties about recursively built structures like lists, trees, and expressions by using induction on their construction instead of just numbers.

The Core Idea

Mathematical induction works great for proving things about natural numbers (0, 1, 2, ...), but in computer science, we often work with data structures that are built recursively—like linked lists, binary trees, or mathematical expressions. Structural induction extends the induction principle to these structures.

Instead of proving something for "n" and then "n+1," you prove:

  1. Base case(s): The property holds for the simplest building blocks (empty list, single leaf node, etc.)
  2. Inductive step: If the property holds for smaller structures, then it holds when you build a larger structure from them

How It Works

Think of it like proving something about LEGOs: if you can show your claim is true for individual LEGO bricks (base case), and you can show that whenever it's true for two existing LEGO constructions, it's also true when you snap them together (inductive step), then it must be true for any LEGO structure you can build.

For example, proving something about all binary trees:

  • Base: Show it's true for an empty tree or single-node tree
  • Inductive hypothesis: Assume it's true for left and right subtrees
  • Inductive step: Prove it's true for a tree built by joining those subtrees under a new root

This mirrors how recursive definitions work: a list is either empty OR an element attached to a smaller list. Structural induction follows that same recursive structure.

Key Takeaway: Structural induction proves properties about recursively defined structures by handling base building blocks and showing that combining valid smaller structures yields valid larger ones.