Mathematical Induction

Principal of mathematical induction

Where P(n) is a function taking a natural number and returning a boolean result:

• Base case If P(1) is true and

• Induction step Whenever P(n) is true, P(n+1) is true

• Conclusion P(n) is true for every natural number n.

For example, 1 + 3 + 5 + ... + (2n-1) = n^2:

• Base case 2x1 – 1 = 1²

• Induction step [ 1 + 3 + 5 + ... + (2n-1) ]+ (2(n+1) -1) = [n² ] 2n +1 = (n+1)²

• Conclusion 1 + 3 + 5 + ... + (2n-1) = n²

Proof of mathematical induction

This is done by showing the smallest x such that not P(x) is proved by P(x-1)

-which is to small to be not P(x) and proves it as P(x) ? P(x + 1)

• 1 Assume P(0)

• 2 Assume for all n = 0, P(n) ? P(n + 1)

• 3 Assume “for all m = 0 (natural numbers), P(m)” is false

• ie There exists an m such that not P(m)

We now prove that if 1 and 2 are true, then 3 is false, hence P(m) is true for all natural numbers

• Let x be the smallest value such that not P(x)

• By rule one, x can't be zero

• As x is the smallest not P, P(x-1), but by 2 this gives a contradiction as P(x) ? P(x + 1)

Course of values induction

• Induction step Whenever P(k) can be inferred from the truth of P(j) for all j < k

• Conclusion P(n) is true for every natural number n

Note the lack of base case