In mathematics, what is meant by induction?

Question

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?

Answer 1

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.

Answer 2

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.