Could someone please explain to me what induction is and give me an example of 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 Î N: P(n) is true}. For example if P(n)=`(n+1)²=n²+2n+1 ' then A={n Î N:(n+1)²=n²+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

n å i=1

i=(n2+n)/2

for every n in N. We apply induction with

P(n)=`

n å i=1

i=(n2+n)/2 '

. There are two steps:

1. Is P(1) true? - Yes because
   

   1 å i=1

   i=1=(12+1)/2

   
   
2. Does P(n)Þ P(n+1) for every n? - Yes because
   

   n+1 å i=1

   i=

   n å i=1

   i + n+1=(n2+n)/2+n+1=((n2+2n+1)+(n+1))/2 = ((n+1)2+(n+1))/2

   
   

Try proving the geometric series sum by induction, show that for any n in N and any real number r (not equal to 1),

n-1 å i=0

ri = (rn-1)/(r-1).