Welcome to NRICH.

 
Definition of Induction
By Marc Carlambe on Monday, August 05, 2002 - 07:27 am:

Could someone please explain to me what induction is and give me an example of it.

By William Astle on Monday, August 05, 2002 - 10:02 am:

Induction is an axiom of the natural numbers N (1, 2, 3, 4, 5....). This means that it is a defining (i.e. assumed) property of the natural numbers. The natural numbers would be different without it.

Suppose we start with a subset A of N i.e. all the things in A are also in N. The induction axiom says if you know 1 is in A and if you can prove that a number n being in A implies that n+1 is also in A then A, is in fact, all of N.

When you are asked to solve a problem, the set A is generally defined by some property P of the numbers it contains. That is to say A = {n in N : P(n) is true}. For example if P(n) = '(n+1)2=n2+2n+1' then A = {n in N : (n+1)2=n2+2n+1} = N since P(n) holds for every natural n.

The important thing, that you need to remember to solve problems, is:

If 1 has a particular property P and the fact that any number n has the property P implies that n+1 has the property P then every natural number has the property P. This is written in mathematical short-hand as:

If P(1) and for all n in N P(n)ÞP(n+1) then P(m) holds for all m in N.

Examples
Suppose you want to prove the statement Sn i=1 i = (n2+n)/2 for every n in N. We apply induction with P(n) = 'Sn i=1 i = (n2+n)/2'. There are two steps:

1) Is P(1) true? - Yes because S1 i=1 i = 1 = (12+1)/2

2) Does P(n) Þ P(n+1) for every n? - Yes because Sn+1 i=1 i = Sn i=1 i + n+1 = (n2+n)/2 + n+1 = ((n2+2n+1)+(n+1))/2 = ((n+1)2+(n+1))/2

That's it.

Try proving the geometric series sum by induction, show that for any n in N and any real number r (not equal to 1), Sn-1 i=0 ri=(rn-1)/(r-1).