section_path: Methods of proof/Proof by mathematical induction
section_name: Proof by mathematical induction
paragraph_text: Proof by mathematical induction
  
  Despite its name, mathematical induction is a method of deduction, not a form of inductive reasoning. In proof by mathematical induction, a single "base case" is proved, and an "induction rule" is proved that establishes that any arbitrary case implies the next case. Since in principle the induction rule can be applied repeatedly (starting from the proved base case), it follows that all (usually infinitely many) cases are provable. This avoids having to prove each case individually. A variant of mathematical induction is proof by infinite descent, which can be used, for example, to prove the irrationality of the square root of two.
  
  A common application of proof by mathematical induction is to prove that a property known to hold for one number holds for all natural numbers: Let N = {1, 2, 3, 4,... } be the set of natural numbers, and let P (n) be a mathematical statement involving the natural number n belonging to N such that
  
  For example, we can prove by induction that all positive integers of the form 2 n − 1 are odd. Let P (n) represent " 2 n − 1 is odd":
  
  The shorter phrase "proof by induction" is often used instead of "proof by mathematical induction".