Induction and Contraditions Flashcards

1
Q

What is proof by induction?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the three steps of proof by induction?

A
  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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly