Editing Mathematical proof (section)

===Proof by mathematical induction===
{{Main|Mathematical induction}}
Despite its name, mathematical induction is a method of [[Deductive reasoning|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 [[Material conditional|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 [[Infinite set|infinitely]] many) cases are provable.<ref>Cupillari, p. 46.</ref> 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 [[Square root of 2#Proofs of irrationality|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 number]]s:<ref>[http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html Examples of simple proofs by mathematical induction for all natural numbers]</ref>
Let {{math|1='''N''' = {1, 2, 3, 4, ...}}} be the set of natural numbers, and let {{math|''P''(''n'')}} be a mathematical statement involving the natural number {{math|''n''}} belonging to {{math|'''N'''}} such that
* '''(i)''' {{math|''P''(1)}} is true, i.e., {{math|''P''(''n'')}} is true for {{math|1=''n'' = 1}}.
* '''(ii)''' {{math|''P''(''n''+1)}} is true whenever {{math|''P''(''n'')}} is true, i.e., {{math|''P''(''n'')}} is true implies that {{math|''P''(''n''+1)}} is true.
* '''Then {{math|''P''(''n'')}} is true for all natural numbers {{math|''n''}}.'''

For example, we can prove by induction that all positive integers of the form {{math|2''n''&nbsp;−&nbsp;1}} are [[parity (mathematics)|odd]].  Let {{math|''P''(''n'')}} represent "{{math|2''n''&nbsp;−&nbsp;1}} is odd":
:'''(i)''' For {{math|1=''n'' = 1}}, {{math|1=2''n''&nbsp;−&nbsp;1&nbsp;=&nbsp;2(1)&nbsp;−&nbsp;1&nbsp;=&nbsp;1}}, and {{math|1}} is odd, since it leaves a remainder of {{math|1}} when divided by {{math|2}}. Thus {{math|''P''(1)}} is true.
:'''(ii)''' For any {{math|''n''}}, if {{math|2''n''&nbsp;−&nbsp;1}} is odd ({{math|''P''(''n'')}}), then {{math|(2''n''&nbsp;−&nbsp;1)&nbsp;+&nbsp;2}} must also be odd, because adding {{math|2}} to an odd number results in an odd number.  But {{math|1=(2''n''&nbsp;−&nbsp;1)&nbsp;+&nbsp;2&nbsp;=&nbsp;2''n''&nbsp;+&nbsp;1&nbsp;=&nbsp;2(''n''+1)&nbsp;−&nbsp;1}}, so {{math|1=2(''n''+1)&nbsp;−&nbsp;1}} is odd ({{math|''P''(''n''+1)}}).  So {{math|''P''(''n'')}} implies {{math|''P''(''n''+1)}}.
:'''Thus''' {{math|2''n''&nbsp;−&nbsp;1}} is odd, for all positive integers {{math|''n''}}.

The shorter phrase "proof by induction" is often used instead of "proof by mathematical induction".<ref>[http://www.warwick.ac.uk/AEAhelp/glossary/glossaryParser.php?glossaryFile=Proof%20by%20induction.htm Proof by induction] {{Webarchive|url=https://web.archive.org/web/20120218033011/http://www.warwick.ac.uk/AEAhelp/glossary/glossaryParser.php?glossaryFile=Proof%20by%20induction.htm |date=February 18, 2012 }}, University of Warwick Glossary of Mathematical Terminology</ref>