Induction and Contraditions Flashcards
1
Q
What is proof by induction?
A
Proving that a certain predicate is true for all natural numbers.
2
Q
What are the three steps of proof by induction?
A
- Basic step - show that P(0) is true
- Inductive step - Show that if P(k) then P(k + 1) holds
- Conclusion - then P(n) must be true for any natural number.
3
Q
What is proof by contradicition?
A
A proof that starts by assuming the opposite proposition is true and then shows that such assumption leads to a contradiction.