In mathematics, what is meant by 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? 
 A: 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.
A: 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.
