1
$\begingroup$

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?

  • 1
    The Wikipedia article on this topic can be useful to read: http://en.wikipedia.org/wiki/Mathematical_induction2012-07-30

2 Answers 2

3

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.

  • 0
    The $\Rightarrow$ means "if ... then" in the sense of "if P(n) is true, then P(n+1) is true".2012-07-30
1

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.