Induction and Contraditions

Question 1

What is proof by induction?

Answer 1

Proving that a certain predicate is true for all natural numbers.

Question 2

What are the three steps of proof by induction?

Answer 2

1. Basic step - show that P(0) is true
2. Inductive step - Show that if P(k) then P(k + 1) holds
3. Conclusion - then P(n) must be true for any natural number.

Question 3

What is proof by contradicition?

Answer 3

A proof that starts by assuming the opposite proposition is true and then shows that such assumption leads to a contradiction.