How does proof by induction work?
In: Mathematics
The proof by induction can be applied on a set, the elements of which can all be obtained from a certain finite number of basic elements and a certain finite number of elementary operations.
On such a set, to prove that all elements of the set have a certain property, it’s sufficient to prove that all basic elements have it, and that it is stable through each elementary operation, which means that, if all operands have the property, then so does the result.
The proof by recurrence is a specific case of proof by induction, where you prove properties on all integers relying on the fact that all integers can be obtained from a basic element (zero) and an elementary operation (the successor, which to n associates n+1).
Latest Answers