1.15 Proof by induction, contradiction and counterexample

1.15 Proof by induction, contradiction and counterexample Flashcards

IB Maths: Analysis and Approaches HL: 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 (n=1n = 1), assumption (P(k)P(k) true), inductive step (show P(k+1)P(k+1)), 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 ∑r=1nr(r+1)\sum_{r=1}^{n} r(r+1), what term do you add to go from n=kn = k to n=k+1n = k+1?
(k+1)(k+2)(k+1)(k+2)
Divisibility step: if 5k−1=4m5^{k} - 1 = 4m, write 5k+1−15^{k+1} - 1 as a multiple of 4.
5(4m+1)−1=4(5m+1)5(4m + 1) - 1 = 4(5m + 1).
What is the first line of a proof by contradiction?
Assume the statement is false (its negation is true).
Key step showing 3\sqrt{3} is irrational?
p2=3q2p^{2} = 3q^{2} so 3 divides pp; then p=3mp = 3m gives q2=3m2q^{2} = 3m^{2}, so 3 divides qq too — contradicting lowest terms.
Outline Euclid's proof that there are infinitely many primes.
Assume finitely many primes p1,…,pnp_1, \ldots, p_n; N=p1⋯pn+1N = p_1\cdots p_n + 1 is not divisible by any of them, so it has a prime factor outside the list — contradiction.
Why is rational + irrational always irrational?
If a+ba + b were rational, b=(a+b)−ab = (a + b) - a would be a difference of rationals, hence rational — contradiction.
Is rational × irrational always irrational?
No: 0×2=00 \times \sqrt{2} = 0 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 'n2+41n+41n^{2} + 41n + 41 is prime for all n∈Z+n \in \mathbb{Z}^{+}'.
n=41n = 41: 412+412+41=41×8341^{2} + 41^{2} + 41 = 41 \times 83, which is not prime.
Can checking many cases prove a statement for all integers?
No. n2+n+41n^{2} + n + 41 is prime for n=1n = 1 to 39 but not for n=40n = 40.

Flashcards