Problem Solving and Proof
What this domain tests
Problem Solving and Proof on PEI Math 521B assesses how you construct and communicate arguments. Questions may ask for a direct proof, a proof by contradiction or contrapositive, an induction, or a disproof by counterexample. Marks depend on logical structure and completeness, so the exam rewards clear statements of assumptions, definitions, and the conclusion reached.
Core rules and concepts
- Direct proof: assume the hypotheses, unpack definitions, and derive the conclusion in explicit steps.
- Contrapositive and contradiction: proving ¬Q ⇒ ¬P establishes P ⇒ Q; contradiction assumes P and ¬Q and derives a falsehood. These are distinct and should be labeled correctly.
- Mathematical induction: prove the base case, assume the statement for n = k, then derive it for k + 1. Strong induction assumes all cases up to k.
- Counterexample: a single valid counterexample disproves a universal claim; it must satisfy the hypotheses and violate the conclusion.
- Quantifiers: "for all" and "there exists" have negations that swap: ¬∀x P(x) is ∃x ¬P(x). Misreading the order of quantifiers changes the claim.
Worked example
Prove that for every integer n, n² + n is even. Direct proof: n² + n = n(n + 1), a product of consecutive integers. One of n and n + 1 is even, so the product is even. Alternatively, induction: for n = 0, 0 is even. Assume k² + k is even; then (k + 1)² + (k + 1) = k² + 2k + 1 + k + 1 = (k² + k) + 2(k + 1), a sum of an even number (by hypothesis) and an even number, hence even. Both arguments are valid; the direct factorization is shorter, while the induction shows the standard structure the exam expects you to be able to write.
Traps that cost marks
- Proving the converse instead of the stated implication, or mislabeling a contradiction proof as direct.
- Omitting the base case in induction, or failing to use the inductive hypothesis in the step.
- Offering a counterexample that does not satisfy the hypotheses, so it disproves nothing.
- Reversing quantifiers, e.g. treating "for every x there is y" as "there is y for every x".