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
Proof by induction proves that one case is true then proves that if it is true for X, it is true for another case (often X+1).
By proving those two things, you can prove it’s true in an infinite number of cases.
Proof by exhaustion proves something is true for every possible case by considering every case or type of case. This is often simpler than proof by induction, but can be more limited.
If you’re proving something is true for all numbers 1-100, proof by exhaustion and a computer is great. If you want to prove it for all natural numbers, you want proof by induction, or some way to narrow it down to use proof by exhaustion (such as modulo mathematics, eg: considering the cases where is even and where it is odd).
Sometimes you might even combine them and use a proof by exhaustion that uses induction for some of the types of cases.
**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.
Proof by exhaustion is when you have a large, but finite number of possibilities, and you show that some statement is true for every single one of them.
For example, let’s say you want to prove that no scrabble word could ever score 2000 points. You do that by making a table of every single scrabble word in the scrabble dictionary, and computing the maximum score if you could place it anywhere you wanted on the scrabble board. If you listed every single word and its position and score, that’d be a proof by exhaustion.
Proof by induction is where you have an infinite number of possibilities, so it’d be impossible to just show them all – they go on forever. But you prove something that’s true by showing the simplest case, then showing how you can use the smaller case to prove the next larger, and so on.
A proof by induction is small. It shows that n=1 is true, and that if n is true then n+1 is true. That means for any n it must be true. It often gives you insight into why it’s always true.
A proof by exhaustion is large. It lists every possible n and shows why it must be true. It tends to not give you any insight into why it’s true because it just treats every example as its own thing rather than finding a general explanation.
Latest Answers