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 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