Trevor Pythagoras

Proof by induction involves proving that if a statement is true in one case then it must also be true for the next case. Then by showing that it is true for a base case, eg 0, you can conclude that it is true for all positive integral cases, since if it is true for case 0 it must be true for case 1 and if it is true for case 1 it must also be true for case 2 etc

To do this it is normal to let Pn be the statement you are trying to prove in a general case n. Let us use the example Pn: 9ⁿ – 1 is divisible by 8 so we may right 9ⁿ-1 = 8a where a is an integer

Then we must prove that if Pk is true Pk+1 is also true. This will require using the expression Pk otherwise it isn’t induction since you are not showing that the truth of each statement can be found from the previous one.

so consider 9^(k+1) – 1
This is equal to 9×9k -1=9×9k – 9+ 8=9(9k-1)+8
but from Pk we know 9k-1 = 8a so
9^k+1-1 = 9(8a)+8=8(9a+1)
which is of the form 8b so is divisible by 8
Hence if Pk “9^k-1 is divisible by 8″ is true then Pk+1 is also true

Finally we must prove that P1 is true and we then know that Pn is true for all k >=1 where k is an integer.

P1 is the statement 9¹ – 1 is divisible by eight
9¹-1=9-1=8 so is true

therefore Pn is true for all positive integral value of n