Proof by induction vs Proof by exhaustion

Question

In my mind they’re literally the same/similar and I cannot wrap my head around it

Tried googling but didn’t help

Please can someone explain the difference?

In: Mathematics

Answer 1

**Proof by Exhaustion** means that you consider a finite fixed list of possibilities and then check truth for each of them. The exhaustiveness is the property that we didn’t miss any case, there is no other option than those listed.

For example, each natural number is either _even_ or _odd_; it is either divisible by 2 or it isn’t. This is the most basic version of exhaustion we meet and covers already the majority of proofs: something is either true, or it isn’t. So say we have to show that no perfect square number is twice an odd number, then we can check those two options (again, note that there is no other!):

– If x is odd, then we note that odd·odd is always odd again. In particular x^2 = x·x is odd and thus not twice any natural number.
– If x is even, then x = 2·y for some natural y and thus x² = 4·y² is divisible by 2 at least twice.

In either case we found that the claim is correct and thus we proved it.

**Proof by induction** is only exhaustive in the sense that it goes over all natural numbers one-by-one without missing any. But the general principle is very different:

Say we have an infinite queue of people. We already know that the person at the front is trustworthy, and each person vouches for the next one behind them to also be trustworthy.

Obviously we cannot blindly trust a potentially non-trustworthy person’s opinion on the guy behind them, and thus begin with our first and so far only certified trustworthy person. They tell us the second in line is also trustworthy, and thus we believe that. Then the second one vouches for the third, which thus gets added to our list of verified trustworthiness. And by their account we now add the fourth, and then the fifth, and so on… and ultimately we can conclude that each single person in the entire line is trustworthy!

As you see, proof by induction does not really distinguish more than “the one at the front” versus “everyone else”. And while this is technically exhaustive, the front one is most often so easy to establish to have what we want that it is barely worth mentioning. One can also wrote induction without distinguishing anyone.