What is mathematical induction
BTW.Mathematical induction means this:
A Brief Review of the Principle of Induction
The principle of mathematical induction says this: Suppose you have a set of natural numbers (natural numbers are the numbers 1, 2, 3, 4, . . . ). Suppose that 1 is in the set. Suppose also that, whenever n is in the set, n+1 is also in the set. Then every natural number is in the set.
To state it more informally: suppose you have the number 1 in your collection, and for each number that you have in the collection, you also have it plus 1 in your collection. Then you have all the natural numbers.
Intuitively, the idea is that if you start with the number 1, and keep on adding 1 to it, you will eventually get to every number.
The principle of induction is extremely important because it allows one to prove many results that are much more difficult to prove in other ways. The most common application is when one has a statement one wants to prove about each natural number. It may be quite difficult to prove the statement directly, but easy to derive the truth of the statement about n+1 from the truth of the statement about n. In that case, one appeals to the principle of induction by showing
The statement is true when n=1.
Whenever the statement is true for one number n, then it's also true for the next number n+1.
If you can prove those two things, then the principle of induction says that the statement must be true for all natural numbers. (Reason: let S be the set of numbers for which the statement is true. Item 1 says that 1 is in the set, and item 2 says that, whenever one number n is in the set, n+1 is also in the set. Therefore, all numbers are in the set).
As an example, consider proving that 1+2+3+· · ·+n = n(n+1)/2. To try to prove that equality for a general, unspecified n just by algebraic manipulations is very difficult. But it's easy to prove by induction, because it's true when n=1 (1 = 1(1+1)/2), and whenever it's true for one number n, that means 1+2+3+· · ·+n = n(n+1)/2, so 1+2+3+· · ·+n+(n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2, so it's also true for n+1. These two facts, combined with the principle of induction, mean that it's true for all n.