Proof Concepts for Discrete Exam 2

√2 is irrational (proof idea)

Suppose not, so √2 = a/b in lowest terms. Then a² = 2b², so a is even; write a = 2k. Then b² = 2k², so b is even too. This contradicts lowest terms.

Infinitely many primes (proof idea)

Suppose not, so the only primes are p1, p2, …, pn. Let N = p1·p2·…·pn + 1. N > 1, so some prime divides N, but each pi leaves remainder 1 when dividing N. Contradiction.

Universal statement

A statement of the form "For all x in D, P(x)." Prove it with a generic particular; disprove it with one counterexample.

Existential statement

A statement of the form "There exists x in D such that P(x)." Prove it by finding one example; disprove it by showing P(x) is false for every x in D.

Generic particular

To prove a property holds for every element of a set, prove it for a particular but arbitrarily chosen element, using only properties that all elements of the set share. Example: "Suppose n is any odd integer."

Method of direct proof

1. Write the statement as "For all x in D, if P(x) then Q(x)." 2. Suppose x is a particular but arbitrarily chosen element of D for which P(x) is true. 3. Use definitions, earlier results, and logic to show that Q(x) is true.

Unpack and repack strategy

Rewrite the hypothesis using definitions (odd becomes 2k + 1), do the algebra, then write the result in the form the target definition needs (for example 2·(integer)), and name that integer, noting it is an integer by closure.

Disproof by counterexample

To show "For all x in D, if P(x) then Q(x)" is false, find one specific x in D for which P(x) is true and Q(x) is false, and verify both.

Constructive proof of existence

Proves an existential statement by actually finding an example, or by giving a method for finding one.

Nonconstructive proof of existence

Shows that an example must exist (for example, using a theorem or a contradiction) without producing a specific one.

Proof by exhaustion

Proves a universal statement over a small finite domain by checking every element one by one.

Common proof mistakes

Arguing from examples; using the same letter for different variables (writing m = 2k and n = 2k); jumping to the conclusion without justification; assuming what is to be proved; writing "if" when you mean "since" or "because."

Proof by division into cases

When the hypothesis splits into possibilities (A1 or A2 or … or An), prove the conclusion C separately in each case. Because the cases cover every possibility, C is true.

When to use division into cases

Parity (n is even or odd), remainders (n mod d = 0, 1, …, d − 1), signs (positive, zero, negative), absolute values, or an "or" in the hypothesis. The cases must cover every possibility.

Proof by contradiction (method)

1. Suppose the statement to be proved is false. 2. Show that this supposition leads logically to a contradiction. 3. Conclude that the statement to be proved is true.

Opening a proof by contradiction

"Suppose not. That is, suppose …" followed by the negation of the statement. For "For all x in D, if P(x) then Q(x)," suppose there is an x in D such that P(x) is true and Q(x) is false.

Negation of "For all x in D, if P(x) then Q(x)"

There exists x in D such that P(x) is true and Q(x) is false.

Negation of "There exists x in D such that P(x)"

For all x in D, P(x) is false.

Proof by contrapositive (method)

For "For all x in D, if P(x) then Q(x)": 1. Rewrite it as "For all x in D, if Q(x) is false then P(x) is false." 2. Prove that by a direct proof: suppose x is an arbitrary element of D for which Q(x) is false, and show P(x) is false.

Contrapositive of "if p then q"

"If not q, then not p." It is logically equivalent to the original statement.

Converse and inverse of "if p then q"

Converse: "if q then p." Inverse: "if not p then not q." Neither is equivalent to the original statement, but they are equivalent to each other.

Relationship between contradiction and contrapositive

A contrapositive proof can always be rewritten as a contradiction proof: suppose P(x) and not Q(x), use the contrapositive argument to derive not P(x) from not Q(x), and note that this contradicts P(x). Contrapositive is the more direct version of the same argument.

When to use contradiction or contrapositive

When the conclusion is a negative ("not," "irrational," "no integer," "infinitely many"), or when assuming the negation gives you something concrete to work with (for example, "suppose it is rational, so it equals a/b"). Use the contrapositive when "not Q" is easier to start from than P.

Classic contrapositive example

For all integers n, if n² is even then n is even. Contrapositive: if n is odd then n² is odd. If n = 2k + 1, then n² = 2(2k² + 2k) + 1, which is odd.

Principle of Mathematical Induction

Let P(n) be a property defined for integers n, and let a be a fixed integer. If P(a) is true, and for every integer k ≥ a, P(k) being true implies P(k + 1) is true, then P(n) is true for all integers n ≥ a.

Basis step

Show that P(a) is true for the starting value a.

Inductive hypothesis (ordinary induction)

The supposition that P(k) is true for a particular but arbitrarily chosen integer k ≥ a.

Inductive step

Show that if P(k) is true (the inductive hypothesis), then P(k + 1) is true. The argument must actually use the inductive hypothesis.

When to use ordinary induction

To prove a statement for all integers n ≥ a when the n = k + 1 case builds directly on the n = k case: sum formulas, inequalities such as 2^n < n!, and divisibility statements such as 3 | (2^(2n) − 1).

Domino analogy for induction

Basis step: the first domino falls. Inductive step: every domino that falls knocks over the next one. Conclusion: every domino falls.

Principle of Strong Mathematical Induction

Let P(n) be a property defined for integers n, and let a and b be fixed integers with a ≤ b. If P(a), P(a + 1), …, P(b) are all true, and for every integer k ≥ b, P(i) being true for all integers i from a through k implies P(k + 1) is true, then P(n) is true for all integers n ≥ a.

Inductive hypothesis (strong induction)

Suppose k ≥ b is any integer and P(i) is true for ALL integers i with a ≤ i ≤ k, not just for i = k.

Ordinary vs. strong induction

Ordinary induction assumes only P(k) to prove P(k + 1). Strong induction assumes P(a), P(a + 1), …, P(k) are all true to prove P(k + 1). Use strong induction when P(k + 1) depends on cases further back than k.

When to use strong induction

Recursive sequences that use two or more earlier terms (such as a_k = a_(k−1) + a_(k−2)); prime factorization (k + 1 = rs with smaller factors); making amounts from fixed coin or stamp values; any time k + 1 breaks into smaller pieces that aren't just k.

Why strong induction can need several base cases

If the inductive step for P(k + 1) uses P(k − 1) or values further back, the first few values can't be reached by the step, so each must be checked directly (for example, check both a_0 and a_1 for a two-term recurrence).

Classic strong induction example

Every integer n ≥ 2 is divisible by a prime. If k + 1 is prime, it divides itself. Otherwise k + 1 = rs with 2 ≤ r ≤ k, so by the inductive hypothesis r is divisible by a prime p, and then p | (k + 1) by transitivity.

Well-Ordering Principle

Every nonempty set of integers that are all greater than or equal to some fixed integer has a least element. It is equivalent to induction and is used in proofs such as the existence part of the Quotient-Remainder Theorem.

Exam proof-writing rules

Complete, grammatically correct sentences. Mathematical notation is allowed, but no logical notation (no ∀, ∃, ⇒, ∴, ∧, ∨, ~). Justify every step. Prove any claim that wasn't proven in class and isn't a basic law of arithmetic. Half of each proof's points are for structure and formality.

Proof structure checklist

Name the method ("We use proof by contradiction"); introduce every variable with its type ("Let n be an integer"); state the assumptions or inductive hypothesis; justify each step with a definition or theorem; end with a concluding sentence.