Proof by Induction

Question 1

Proofs

Answer 1

Proof by exhaustion - prove true for all possible values by splitting it up into e.g. even and odd
Proof by deduction - Work from things you know are true and show it is true
Proof by contradiction - Prove that the opposite is false
Disproof by counter-example - Find just one case where it is false

Question 2

Proof by induction

Answer 2

1) Show that the statement is true for n = 1
2) Assume that it is true for n = k
3) Prove it is true for n = k + 1, if it is true for n = k
4) Write a concluding statement along the lines of ‘The statement is true for n = 1, and it is true for n = k + 1 when it is true for n = k, therefore it must be true for all n ≥ 1’