proof by recursion also called proof by mathematical induction, a method for conclusively demonstrating the truth of universal propositions about the natural numbers. The system of (natural) numbers is construed as an infinite sequence of elements beginning with the number 1 and such that each subsequent element is the (immediate) successor of the preceding element. The (immediate) successor of a number is the sum of that number with 1. In order to apply this method to show that every number has a certain chosen property it is necessary to demonstrate two subsidiary propositions often called respectively the basis step and the inductive step. The basis step is that the number 1 has the chosen property; the inductive step is that the successor of any number having the chosen property is also a number having the chosen property (in other words, for every number n, if n has the chosen property then the successor of n also has the chosen property). The inductive step is itself a universal proposition that may have been proved by recursion. The most commonly used example of a theorem proved by recursion is the remarkable fact, known before the time of Plato, that the sum of the first n odd numbers is the square of n. This proposition, mentioned prominently by Leibniz as requiring and having demonstrative proof, is expressed in universal form as follows: for every number n, the sum of the first n odd numbers is n2. 1 % 12, (1 ! 3) % 22, (1 ! 3 ! 5) % 32, and so on. Rigorous formulation of a proof by recursion often uses as a premise the proposition called, since the time of De Morgan, the principle of mathematical induction: every property belonging to 1 and belonging to the successor of every number to which it belongs is a property that belongs without exception to every number. Peano (1858–1932) took the principle of mathematical induction as an axiom in his 1889 axiomatization of arithmetic (or the theory of natural numbers). The first acceptable formulation of this principle is attributed to Pascal.
See also DE MORGAN, OMEGA, PHILOSOPHY OF MATHEMATIC. J.Cor.