University Discrete Mathematics — Methods of Proof Worksheet

All 10 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one.

1. Q1Direct Proof

   An integer $n$ is even if $n=2k$ for some integer $k$, and odd if $n=2k+1$ for some integer $k$. Give a direct proof of the following statement.

   If $m$ and $n$ are odd integers, then $mn+m+n$ is odd.

2. Q2Direct Proof

   For integers $a$ and $b$, we write $a\mid b$ (“$a$ divides $b$”) when $b=ak$ for some integer $k$.

   1. Check the statement below for $a=3$, $b=6$, $c=12$.
   2. Give a direct proof: for all integers $a$, $b$, $c$, if $a\mid b$ and $b\mid c$, then $a^2\mid bc$.
3. Q3Proof by Contraposition

   Let $n$ be an integer. Consider the statement “if $5n+3$ is even, then $n$ is odd.”

   1. Write its contrapositive and its converse.
   2. Prove the statement by contraposition. (An integer is even if it equals $2k$, odd if it equals $2k+1$, for some integer $k$; every integer is exactly one of the two.)
4. Q4Proof by Contraposition

   Let $x$ and $y$ be real numbers. Prove by contraposition: if $x+y>10$, then $x>5$ or $y>5$. Begin by writing the contrapositive, negating the “or” correctly.

5. Q5Proof by Contradiction

   Each statement below is to be proved by contradiction.

   1. There is no largest odd integer. Write the assumption the proof starts from.
   2. If $a$, $b$, $c$ are integers and $a+b+c$ is odd, then at least one of $a$, $b$, $c$ is odd. Write the assumption the proof starts from.
   3. For every real number $x>0$, $x+{\displaystyle \frac{4}{x}}\ge 4$. Write the assumption the proof starts from, then complete the proof.
6. Q6Proof by Contradiction

   Prove by contradiction that there are no integers $a$ and $b$ with $a^2-4b=2$. You may use the fact that if $a^2$ is even, then $a$ is even.

7. Q7Proof by Cases

   An integer is even if it equals $2k$, and odd if it equals $2k+1$, for some integer $k$; every integer is one or the other. Prove by cases that for every integer $n$, the number $n^2+3n+5$ is odd.

8. Q8Proving an If and Only If Statement

   Let $x$ be a real number. Prove that $$x^2-4x+3<0\text{if and only if}1<x<3,$$ proving each direction separately and saying which direction is which.

9. Q9Existence Proofs and Counterexamples

   A prime is an integer $p>1$ whose only positive divisors are $1$ and $p$. Here $\mathbb{N}=\{0,1,2,\dots \}$ and ${\mathbb{Z}}^{+}=\{1,2,3,\dots \}$.

   1. Disprove: for every $n\in \mathbb{N}$, the number $2^n+1$ is prime.
   2. Disprove: for all real numbers $a$ and $b$, $(a+b{)}^2\ge a^2+b^2$.
   3. Prove: there exist distinct $m,n\in {\mathbb{Z}}^{+}$ with $m^n=n^m$.
10. Q10Synthesis — drawing on several topics in this unit

    Every integer $n$ can be written in exactly one of the forms $3k$, $3k+1$ or $3k+2$ with $k$ an integer. We write $3\mid n$ when $n=3k$ for some integer $k$.

    1. Prove by cases that for every integer $n$: if $n=3k$ then $n^2=3q$ for some integer $q$, and if $n=3k+1$ or $n=3k+2$ then $n^2=3q+1$ for some integer $q$.
    2. Deduce from (a), by contraposition, that for every integer $n$, if $3\mid n^2$ then $3\mid n$.

The 7 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

Direct proof, and the definitions that make it possible

A direct proof assumes the hypothesis and argues forward to the conclusion. Nothing about it is clever; what makes it work is refusing to use any word whose definition you have not written down. Q1 and Q2 both hand you the definitions in the question itself — even, odd, and a divides b — which is a signal that the definitions are meant to be the first line of your work.

Q1 is that skeleton with nothing in the way. Two odd integers come in, an expression built from them goes out, and the whole proof is substitution followed by grouping. The step people skip is the last one: the algebra is finished, the required form is on the page, and the sentence naming the integer is missing.

Q2 adds the divides relation and splits into two parts that do different jobs. Part (a) asks you to check the statement on particular numbers: substitute them into each hypothesis, name the integer multiplier each one needs, and then do the same for the conclusion. Part (b) is the proof itself, for all integers. Translate each hypothesis into an equation with its own named multiplier, substitute one into the other to get an expression for the quantity you care about, and then group it so the required divisibility is visible.

Proof by contraposition

A conditional and its contrapositive are logically equivalent, so proving one proves the other. That is the entire justification for the method, and it is worth writing out once: you are allowed to prove a different statement because the previous set established that it is the same statement.

Q3 makes the distinction explicit before anything is proved. Part (a) asks for the contrapositive and the converse of a statement about 5n + 3. Build each mechanically: identify the hypothesis p and the conclusion q first, then swap them for the converse, and swap and negate both for the contrapositive. Negating "n is odd" uses a fact the question supplies: an integer that fails to be odd has to be even, the two possibilities being exclusive and leaving nothing out. That is what makes the negation a usable sentence rather than a phrase with "not" in front of it.

Part (b) is then a direct proof of the contrapositive: start from the negated conclusion, write that integer in the form its definition gives, substitute into the expression, and reach the negated hypothesis. Say at the top which statement you are proving and why that settles the original. A proof of the contrapositive that never announces itself reads like a proof of the converse.

Q4 moves to real numbers and turns on the negation rather than on the algebra. The conclusion is an "or", and the negation of an "or" is an "and" — De Morgan, from the previous set — so the contrapositive assumes two things at once rather than one. Negate each strict inequality carefully: the opposite of x > 5 is x ≤ 5, not x < 5. Once both bounds are assumed, the proof needs one move only, and it is the move that two inequalities pointing the same way allow.

Proof by contradiction: choosing the assumption

A proof by contradiction assumes the statement is false, derives something impossible, and concludes that the assumption was. Almost all of the difficulty is in the first line, which is why Q5 asks for that line three times and only completes one of the proofs.

Q5(a) negates a statement that denies an object exists, so the assumption hands you one to work with. Q5(b) negates a conditional: the hypothesis stays, and it is the conclusion that flips — and since that conclusion says "at least one", the negation is a statement about all three numbers. Q5(c) negates a "for every" over the positive reals, which yields one particular number with a reversed inequality, and then asks you to finish. Clear the fraction by multiplying through by that number, which is legitimate and leaves the inequality pointing the same way because it is positive; bring everything to one side; factor the quadratic that appears; and compare the sign you have assumed with the sign that expression is capable of having.

Q6 is a full contradiction proof about an equation in two integers, and it comes with a fact you are allowed to use: if a square is even then the number itself is even. That fact is a bridge. Assume integers satisfying the equation exist, rearrange so that the square stands alone and its parity can be read off the other side, apply the supplied fact to learn the parity of the number itself, write it in the form that parity gives, and substitute it back into the original equation. Then divide through by the common factor and read the parity of each side. The contradiction is a statement about parity, not about the size of anything.

Proof by cases

Splitting into cases is allowed as long as the cases are exhaustive: every object the statement is about must fall into at least one of them. Q7 is about every integer, and the question states the split it wants — every integer is even or odd — so the exhaustiveness is handed to you and the work is doing the same algebra twice.

In Q7 the expression is a quadratic in n, so each case is an expansion followed by a grouping. Keep the target form in front of you — an integer is odd when it can be written as twice an integer, plus one — and stop when the expression is in it, naming the integer as in Q1.

Proving an if and only if statement

An if and only if is two conditionals, and the standard way to prove one is to prove each direction separately and label it. Q8 says so explicitly: prove both directions and say which is which.

The statement in Q8 relates a quadratic inequality to a pair of bounds on x. Factor the quadratic first; after that both directions are arguments about the signs of two factors, since a product of two real numbers is negative exactly when the two have opposite signs. Going one way, you know the product's sign and must locate x; coming back, you know where x sits and must determine each factor's sign and then their product's. Each direction is a few lines, and each needs its own opening sentence naming what is assumed and what is to be shown.

Existence proofs and counterexamples

A statement about all objects is destroyed by one object that fails it. A statement that some object exists is established by one object that works. Q9 has both kinds, three times over, and the asymmetry is the lesson: to disprove a "for all" you exhibit, and to prove a "there exists" you also exhibit.

Q9(a) asks you to disprove a claim that a certain family of numbers is always prime. Read the definition of prime the question gives, note which values the question's own definition of the number set allows — it says where the index starts — and test them in order. A counterexample is not complete until you have shown the number fails the definition, which for a primality claim means writing the number as a product of two smaller positive integers, or pointing to a divisor other than 1 and itself.

Q9(b) disproves an inequality claimed for all real a and b. Expand the left side and set it beside the right: the two differ by a single term, so the entire question is whether that term can have the wrong sign, and the counterexample is any pair of numbers that makes it do so. Having chosen the pair, compute both sides and write them next to each other — the reader has to see the inequality fail, not be told it does.

Q9(c) is a genuine existence proof: distinct positive integers with a certain relation between them. The honest method is a constructive one — search small values systematically, and when a pair works, present it and verify the relation by computing both sides. An existence proof does not have to explain how the object was found, but it does have to check that it qualifies, including any side condition such as the two being distinct.

The synthesis question

Q10 uses two of the methods on one problem, and the second part depends on the first. It works with the three forms an integer can take relative to 3 — the question states them and states that every integer takes exactly one — which is a proof by cases with three cases instead of two.

Part (a) is that proof by cases: square each of the three forms, expand, and group the result into the form the statement asks for, naming the integer each time exactly as in Q1 and Q7. Three cases means three complete arguments, and two of them will land on the same form, which is worth remarking rather than hiding.

Part (b) asks you to deduce a divisibility statement by contraposition. Write the contrapositive of the statement first, as in Q3(a); it is a claim about the integers that are not multiples of 3, and those are exactly the two forms part (a) already handled. So the work is not new algebra but an argument about coverage: name the cases of (a) you are invoking, say why together they account for every integer of that kind, and say why what (a) establishes about them gives what the contrapositive claims. Then close by stating that the contrapositive is equivalent to the original.

Preview all 5 pages

Click any page to open the full PDF.

Getting the most out of it

Write the definition before you write the proof

Even, odd, divides, prime: each of these is an equation or a condition, and a proof that uses one without writing it down has nothing to manipulate. Put the definitions of every term in the statement at the top of the page, then start. This alone fixes most stalled proofs.

Say what you are assuming and what you are showing

Every proof here opens with one sentence — "assume m and n are odd", "suppose for contradiction that such integers exist", "we prove the contrapositive" — and closes with one. Written work in this course is marked on the quality of the expression as well as the mathematics, and those two sentences are where a correct calculation turns into a proof.

Practise negating before you practise proving

Take any statement on the sheet and write its negation, its converse and its contrapositive, without proving anything. Contradiction and contraposition are only as good as that step, and it is the step that carries the "or", "at least one" and "for every" traps from the previous set into this one.

Choose the method deliberately, and say why

Before writing, ask three questions. Is the conclusion an "or", or a negation? Try contraposition. Is the statement a denial that something exists? Try contradiction. Does the object have finitely many forms? Try cases. A line naming the method and the reason costs nothing and organises everything after it.

Reread your proof as someone who does not believe it

Check for the specific failures: two objects given the same letter, an "or" negated as an "or", a case left out, a step that reverses only in one direction, a counterexample asserted but not verified. Each of them leaves a proof that reads convincingly and is wrong.

Common questions