Editing Mathematical induction (section)

{{Short description|Form of mathematical proof}}
{{Distinguish|inductive reasoning}}
{{Use dmy dates|date=February 2021}}
[[Image:Dominoeffect.png|thumb|right|Mathematical induction can be informally illustrated by reference to the sequential effect of [[Domino toppling|falling dominoes]].<ref>Matt DeVos, [https://www.sfu.ca/~mdevos/notes/graph/induction.pdf ''Mathematical Induction''], [[Simon Fraser University]]</ref><ref>Gerardo con Diaz, ''[http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf Mathematical Induction] {{Webarchive|url=https://web.archive.org/web/20130502163438/http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf |date=2 May 2013 }}'', [[Harvard University]]</ref>]]

'''Mathematical induction''' is a method for [[mathematical proof|proving]] that a statement <math>P(n)</math> is true for every [[natural number]] <math>n</math>, that is, that the infinitely many cases <math>P(0), P(1), P(2), P(3), \dots</math>&thinsp; all hold. This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:
{{Blockquote 
|text=Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the '''basis''') and that from each rung we can climb up to the next one (the '''step'''). 
|source=''[[Concrete Mathematics]]'', page 3 margins.
}}

A '''proof by induction''' consists of two cases. The first, the '''base case''', proves the statement for <math>n = 0</math> without assuming any knowledge of other cases. The second case, the '''induction step''', proves that ''if'' the statement holds for any given case <math>n = k</math>, ''then'' it must also hold for the next case <math>n = k + 1</math>. These two steps establish that the statement holds for every natural number <math>n</math>. The base case does not necessarily begin with <math>n = 0</math>, but often with <math>n = 1</math>, and possibly with any fixed natural number <math>n = N</math>, establishing the truth of the statement for all natural numbers <math>n \geq N</math>.

The method can be extended to prove statements about more general [[well-founded]] structures, such as [[tree (set theory)|trees]]; this generalization, known as [[structural induction]], is used in [[mathematical logic]] and [[computer science]]. Mathematical induction in this extended sense is closely related to [[recursion]]. Mathematical induction is an [[inference rule]] used in [[formal proof]]s, and is the foundation of most [[Correctness (computer science)|correctness]] proofs for computer programs.<ref>
{{cite book
 | last = Anderson
 | first = Robert B.
 | title = Proving Programs Correct
 | publisher = John Wiley & Sons
 | year = 1979
 | location = New York
 | page = [https://archive.org/details/provingprogramsc0000ande/page/1 1]
 | url =https://archive.org/details/provingprogramsc0000ande
 | url-access = registration
 | isbn = 978-0471033950
 }}</ref>

Despite its name, mathematical induction differs fundamentally from [[inductive reasoning]] as [[Problem of induction|used in philosophy]], in which the examination of many cases results in a probable conclusion. The mathematical method examines infinitely many cases to prove a general statement, but it does so by a finite chain of [[deductive reasoning]] involving the [[Variable (mathematics)|variable]] <math>n</math>, which can take infinitely many values. The result is a rigorous proof of the statement, not an assertion of its probability.<ref>{{cite web| url=http://www.earlham.edu/~peters/courses/logsys/math-ind.htm| title=Mathematical Induction| last=Suber| first=Peter| publisher=Earlham College| access-date=26 March 2011| archive-date=24 May 2011| archive-url=https://web.archive.org/web/20110524104121/http://www.earlham.edu/~peters/courses/logsys/math-ind.htm| url-status=dead}}</ref>