A: Proof flashcards

Topic 2: A: Proof

What is a mathematical proof?

A chain of logical steps from given assumptions to a conclusion, valid for every case the statement covers. Testing a few values is evidence, not proof.

Proof by deduction

Argue directly from known facts and definitions to the result, one valid step at a time.

Prove that the sum of three consecutive integers is a multiple of 3.

Let the integers be n, n + 1, n + 2 (n ∈ ℤ). Sum = 3n + 3 = 3(n + 1). Since n + 1 is an integer, the sum is a multiple of 3.

Proof by exhaustion

Split all possibilities into a finite set of cases (for example n even and n odd) and prove each one. State that the cases cover everything.

Disproof by counter-example

Find one case that meets the conditions of the statement but where the conclusion fails. One correct counter-example is enough to disprove it.

Proof by contradiction

Assume the statement is false, reason to something impossible, and conclude that the statement must be true.

Rational and irrational numbers

Rational: can be written a/b with a ∈ ℤ and b ∈ ℤ⁺. Irrational: cannot be written in this form (for example √2 and π).

Outline the proof that √2 is irrational.

Assume √2 = a/b in lowest terms. Then a² = 2b², so a² is even and a is even: a = 2k. Then 4k² = 2b², so b² = 2k² and b is even. Both even contradicts lowest terms, so √2 is irrational.

Outline the proof that there are infinitely many primes.

Assume there are finitely many, p₁, p₂, …, pₙ. Let N = p₁p₂…pₙ + 1. Dividing N by any pᵢ leaves remainder 1, so N has a prime factor not in the list (or is prime itself). Contradiction.

How do you write an even number, an odd number and two different odd numbers in a proof?

Even: 2n. Odd: 2n + 1 (n ∈ ℤ). Two different odd numbers: 2m + 1 and 2n + 1 (m, n ∈ ℤ), not 2n + 1 twice.