I was going through MIT video lectures on "Introduction to Algorithms " . In order to solve recurrences by substitution the professor says that we can solve them by induction.
What is actually the principle behind induction?
I was going through MIT video lectures on "Introduction to Algorithms " . In order to solve recurrences by substitution the professor says that we can solve them by induction.
What is actually the principle behind induction?
The most basic principle is this:
For any proposition P, which is a function from the natural numbers (1,2,...) to a boolean, if:
- P(n) $\Rightarrow$ P(n+1) for all n, and
- P(1)
then P(n) for every n.
That is, if you can prove the base case P(1), and you can prove the implication P(n) $\Rightarrow$ P(n+1) for every n, then you have proved that P holds for all natural numbers.
Mathematical induction, strictly speaking, isn't a form of inductive reasoning. Indeed, it really isn't inductive at all. Essentially, the idea is that if you have that some statement is true for a 'base case' m and you suppose that the claim holds for some arbitrary n≥m, and show that this implies that it holds for n+1, then you've done it. Essentially, this is "bootstrapping." If you want, you can prove it rigorously, using the well ordering principle.
Well ordering principle: Any set of natural numbers has a smallest element. Prove the method works by contradiction.
Please note, however, that this question could have been answered by googling any of the following terms: "mathematical induction," "math induction" ect.