How does structural induction work?

566 views

How does structural induction work?

In: Mathematics

Anonymous 0 Comments

Say you have a structure that’s defined in terms of smaller versions of itself. For example, a binary tree is defined by a root with two smaller binary trees hanging off it, or an arithmetic expression is a collection of expressions joined with {+, -, *, /}. We might want to prove something about all binary trees or all arithmetic expressions. Structural induction is a powerful tool we can use.

First, we need to find a base case. That could just be a tree with no nodes or an expression with just one number. It’s usually really easy to prove something for the base case.

Next, we assume that we’ve solved the problem for all the smaller cases. So we need to show our statement holds when adding one additional step. So if something is true about all smaller trees, then it’s also true when we take two trees (where the statement is true) and hang them off another node.

And that’s all you need. A statement about a particular structure is true because it’s true for each of the smaller structures, and it’s true for each of those because it’s true for the smaller structures inside that, and so on until we hit our base cases. So this proves the statement for all cases.