---
Video Title: Using the Induction Principle
Description: Theory of Computation
https://uvatoc.github.io

3.4: Using the Induction Principle

David Evans and Nathan Brunelle
University of Virginia
---

Now we have a way to do proofs by
induction.

Because all we are doing is now picking a
predicate.

What does it mean to say a predicate?

That is just a function that is a boolean
function on a natural number.

The predicate says we're going to take all
the natural numbers, and the predicate

takes a natural number in, and outputs
true or false.

That predicate defines a subset.

It defines a subset of all the values that
the predicate is true for.

X is the subset that the predicate is true
for.

And then we just have to translate those
two steps.

We have to show that zero is in the set.

Showing the predicate holds for zero is
the equivalent of showing zero is in X.

And showing this is the equivalent of step
two above.

We have a proof technique that works for
any predicate we pick.

As long as we show those two things, we've
shown it holds for all the natural numbers.

Well, there's nothing really special about
zero.

We could start from
something other than zero

and prove for all
numbers above that value.

But we're not going to be proving for zero
if we don't start from zero.

The challenge to get proofs by induction
to work is you've got to actually do that.

You've got to do what's usually the hard
part is this step two.

Prove that the
predicate being true for N

implies that it's true
for the successor of N.