How does proof by induction work?
In: Mathematics
Think of proof by induction like those things where you line up a bunch of dominoes and they knock each other over.
You want to prove that every natural number n has some property P. The two steps of an induction proof are:
The base case: you prove that 1 (or sometimes 0) has property P. This is like knocking over the first domino.
The induction step: you show that n+1 has property P whenever n does. This is like showing that each domino is close enough to the next to knock it over.
Since you’ve knocked the first domino over, and shown that the dominoes are all close enough to each other, you know that every domino will fall over. So every n has property P.
Latest Answers