1.15 Proof by induction, contradiction and counterexample Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What are the four parts of a proof by induction?
- Basis (), assumption ( true), inductive step (show ), conclusion.
- Why write 'assume P(k) is true' rather than 'let n = k'?
- The inductive step depends on an assumption; 'let n = k' does not state what is being assumed and loses the mark.
- In , what term do you add to go from to ?
- Divisibility step: if , write as a multiple of 4.
- .
- What is the first line of a proof by contradiction?
- Assume the statement is false (its negation is true).
- Key step showing is irrational?
- so 3 divides ; then gives , so 3 divides too — contradicting lowest terms.
- Outline Euclid's proof that there are infinitely many primes.
- Assume finitely many primes ; is not divisible by any of them, so it has a prime factor outside the list — contradiction.
- Why is rational + irrational always irrational?
- If were rational, would be a difference of rationals, hence rational — contradiction.
- Is rational × irrational always irrational?
- No: is rational (it is true for non-zero rationals).
- How many counterexamples are needed to disprove a 'for all' statement?
- One — but you must show why it fails the statement.
- Give a counterexample to ' is prime for all '.
- : , which is not prime.
- Can checking many cases prove a statement for all integers?
- No. is prime for to 39 but not for .