\( \newcommand{\mc}{\mathcal} \newcommand{\bb}{\mathbb} \newcommand{\powerset}[1]{\mathbb{P}\left(#1\right)} \newcommand{\set}[2]{\left\{#1:#2\right\}} \newcommand{\genrel}[2]{\left\langle#1:#2\right\rangle} \newcommand{\id}{\operatorname{id}} \newcommand{\dom}{\operatorname{dom}} \newcommand{\cod}{\operatorname{cod}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}_0} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\abs}{\operatorname{abs}} \newcommand{\mat}[3]{\mathbb{M}_{#3}(#1, #2)} \newcommand{\gl}[2]{\operatorname{GL}_{#2}(#1)} \newcommand{\sl}[2]{\operatorname{SL}_{#2}(#1)} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\sgn}{\operatorname{sgn}} \)

Diagnostic Problems for Proof-based Courses

This page contains a running list of problems I give to students to help check their understanding of proof techniques. The manipulations required are routine, and only simple definitions are necessary to write a good proof for most of the problems.

Proofs (and disproofs) for these statements can be read by clicking on the corresponding word.1

Proof by Induction

Prove that \( \sum_{k=1}^n k = \frac{n(n+1)}{2} \) for all \( n \in \bb{Z}_{\geq 0} \) by induction.

Proof.
We proceed by induction on \( n \in \Z_{\geq 0} \).

Base Case: When \( n = 0 \) we have \( \sum_{k=1}^n k = \sum_{k=1}^0 k = 0 \), as this is the empty sum. Moreover, \( \frac{n(n+1)}{2} = \frac{0(0+1)}{2} = 0 \). Hence the base case \( n = 0 \) holds.

Inductive Step: As our inductive hypothesis, we suppose that \( \sum_{k=1}^n k = \frac{n(n+1)}{2} \). Using this hypothesis and basic arithmetic we compute as follows.

\begin{align*} \sum_{k=1}^{n+1} k & = \sum_{k=1}^n k + (n+1) &&\text{(split last term)} \\ & = \frac{n(n+1)}{2} + (n+1) &&\text{(inductive hypothesis)} \\ & = \frac{n(n+1) + 2(n+1)}{2} &&\text{(basic arithmetic)} \\ & = \frac{(n+1)(n+2)}{2} &&\text{(factor)} . \end{align*}

Hence we have verified the inductive step.

As both the base case and inductive step hold, the original statement follows by weak mathematical induction.

Set Theory

Let \( A \) and \( B \) be arbitrary sets. Prove or disprove: \( A \cap B = A \) if and only if \( A \subseteq B \).

Proof.
Let \( A \) and \( B \) be arbitrary sets.

\( \Rightarrow \): Suppose \( A \cap B = A \), and let \( x \in A \) be arbitrary. By definition of set equality, we have \( A \cap B \subseteq A \) and \( A \subseteq A \cap B \). As \( A \subseteq A \cap B \), we have \( x \in A \cap B \) by definition of the subset relation. By definition of set intersection, we have \( x \in A \) and \( x \in B \). Thus \( x \in B \). As \( x \) was arbitrary, we have shown that \( x \in A \) implies \( x \in B \) for all \( x \). Hence \( A \subseteq B \) by definition of the subset relation.

\( \Leftarrow \): Suppose \( A \subseteq B \). To finish the proof, we must show \( A \subseteq A \cap B \) and \( A \supseteq A \cap B \).

\( \subseteq \): Let \( x \in A \) be arbitrary. Thus \( x \in B \) by definition of the subset relation. As \( x \in A \) and \( x \in B \), we have \( x \in A \cap B \) by definition of set intersection. As \( x \) was arbitrary, we see \( A \subseteq A \cap B \).

\( \supseteq \): Let \( x \in A \cap B \) be arbitrary. By definition of set intersection, \( x \in A \) and \( x \in B \). Thus \( x \in A \). As \( x \) was arbitrary, we see \( A \cap B \subseteq A \).

Hence, as both the sufficiency and necessity statements hold, the biconditional holds and the proof is complete.

Counterexample

The header kind of spoils these problems… Students don't know in advance that these statements are false.

Let \( a, b, c \in \bb{Z} \) be arbitrary. Prove or disprove: \( ac \mid bc \) implies \( a \mid b \).

Example.
Let \( a = 2 \), \( b = 1 \), and \( c = 0 \). Then \( ac = 0 = bc \), so \( ac \mid bc \). On the other hand, \( 2 \not \mid 1 \), so \( a \not \mid b \). As the hypothesis of this implication holds and the conclusion does not in this example, we see that the original statement is false.

Proof by Contradiction

Prove that for all \( x, y \in \bb{R} \), if \( x + y \) is irrational, then either \( x \) is irrational or \( y \) is irrational via proof by contradiction.

This problem has a more natural proof using a Proof of Contrapositive: understanding the difference in these methods is important!

Proof.
Let \( x, y \in \R \) be arbitrary, and suppose \( x + y \) is irrational. Assume to the contrary that both \( x \) and \( y \) are rational. By definition of rationality, there are integers \( a, c \in \Z \) and \( b, d \in \Z_{>0} \) such that \( x = \frac{a}{b} \) and \( y = \frac{c}{d} \). Now we compute the sum

\begin{equation} x + y = \frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd} \end{equation}

by basic arithmetic. As \( b, d > 0 \), we have \( bd \in \Z_{>0} \) by order properties of \( \Z \). Moreover, \( ad + bc \in \Z \) by closure properties of \( \Z \). In particular, we have shown that \( x + y = \frac{ad + bc}{bd} \) is a rational number by definition of rationality. However, this directly contradicts the assumption that \( x + y \) was irrational. Hence, we conclude that our assumption that \( x \) and \( y \) are both rational must be false. In particular, at least one of \( x \) or \( y \) is irrational, as claimed.

Proof by Cases

Prove or disprove: \( 3 \mid n(n+1)(n+5) \) for all \( n \in \bb{Z} \).

Note that this can also be proved via two inductive arguments, but two are necessary because \( \Z \) is not well-ordered.

Proof.
Let \( n \in \Z \) be arbitrary. By the Quotient–Remainder Theorem, there are unique \( q, r \in \Z \) satisfying both \( n = 3q+r \) and \( 0 \leq r < 3 \). Thus \( r \in \{0, 1, 2\} \), and we proceed by cases to show that \( n(n+1)(n+5) = 3k \) for some \( k \in \Z \).

Case 0: If \( r = 0 \), then \( n = 3q+0 = 3q \). Noting that \( k = q(n+1)(n+5) \in \Z \) by closure properties of \( \Z \), we have \( n(n+1)(n+5) = 3q(n+1)(n+5) = 3k \).

Case 1: If \( r = 1 \), then \( n+5 = (3q+1)+5 = 3(q+2) \) by basic arithmetic. Noting that \( k = n(n+1)(q+2) \in \Z \) by closure properties of \( \Z \), we have \( n(n+1)(n+5) = 3n(n+1)(q+2) = 3k \).

Case 2: If \( r = 2 \), then \( n+1 = (3q+2)+1 = 3(q+1) \) by basic arithmetic. Noting that \( k = n(q+1)(n+5) \in \Z \) by closure properties of \( \Z \), we have \( n(n+1)(n+5) = 3n(q+1)(n+5) = 3k \).

Thus in all cases we have shown that there is a \( k \in \Z \) such that \( n(n+1)(n+5) = 3k \). By the definition of divisibility, we thus have \( 3 \mid n(n+1)(n+5) \) as claimed.

Footnotes:

1

In related news: I've now learned more HTML than I ever cared to…