this process will not prove the formula for all values of n . What is needed is some kind of chain reaction which will MATHEMATICS have the effect that once the formula is proved for a particular positive integer the formula will automatically follow for the next positive integer and the next indefinitely. Such a reaction may be considered as produced by the method of mathematical induction. .
The Principle of Mathematical Induction Suppose there is a given statement P( n ) involving the natural number n such that ( i ) The statement is true for n = , i.e., P ( ) is true, and ( ii ) If the statement is true for n = k ( where k is some positive integer ), then the statement is also true for n = k + , i.e., truth of P ( k ) implies the truth of P ( k + ). Then, P(n) is true for all natural numbers n. Property (i) is simply a statement of fact. There may be situations when a statement is true for all n ≥ .
In this case, step will start from n = and we shall verify the result for n = , i.e., P( ). Property (ii) is a conditional property. It does not assert that the given statement is true for n = k , but only that if it is true for n = k , then it is also true for n = k + . So, to prove that the property holds , only prove that conditional proposition: If the statement is true for n = k , then it is also true for n = k + .
This is sometimes referred to as the inductive step. The assumption that the given statement is true for n = k in this inductive step is called the inductive hypothesis . For example, frequently in mathematics, a formula will be discovered that appears to fit a pattern like = = = = + =