Mathematical Proof Techniques College Reference Cheat Sheet

Mathematical proof techniques are the standard tools used to justify claims in higher mathematics. This cheat sheet organizes the major methods students use in discrete math, abstract algebra, analysis, number theory, and proof-based courses. It helps students choose an appropriate proof strategy, structure an argument clearly, and avoid common logical errors.

The focus is on readable college-level reference notes rather than memorizing isolated facts.

Core implication methods prove statements of the form $P \Rightarrow Q$ by direct reasoning, contrapositive proof, contradiction, or cases. Induction methods prove statements indexed by natural numbers, usually by establishing a base case and an induction step. Existence and construction proofs show that at least one object satisfies a property, while uniqueness proofs show that no two different objects can satisfy it.

Disproof usually requires only one valid counterexample to a universal claim.

Key Facts

A direct proof of $P \Rightarrow Q$ assumes $P$ is true and uses definitions, known results, and valid algebra to derive $Q$ .
A contrapositive proof uses the logically equivalent statement $\neg Q \Rightarrow \neg P$ to prove $P \Rightarrow Q$ .
A proof by contradiction assumes $P$ is true and $Q$ is false, then derives an impossibility such as $R \land \neg R$ .
To prove $\forall x \in S,\ P(x)$ by cases, split $S$ into exhaustive cases $S_1, S_2, \ldots, S_k$ and prove $P(x)$ in every case.
Weak induction proves $P(n)$ for all $n \geq n_0$ by proving $P(n_0)$ and then proving $P(k) \Rightarrow P(k+1)$ for every $k \geq n_0$ .
Strong induction proves $P(n)$ for all $n \geq n_0$ by proving base cases and then proving $P(n_0) \land \cdots \land P(k) \Rightarrow P(k+1)$ .
An existence proof establishes $\exists x \in S$ such that $P(x)$ , either by constructing such an $x$ or proving one must exist indirectly.
To prove uniqueness, first prove existence of an object $x$ with property $P(x)$ , then prove that if $P(a)$ and $P(b)$ , then $a=b$ .

Vocabulary

Implication: An implication is a statement of the form $P \Rightarrow Q$ , meaning that whenever $P$ is true, $Q$ must also be true.
Contrapositive: The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ , and it is logically equivalent to the original implication.
Contradiction: A contradiction is a statement that cannot be true, such as $R \land \neg R$ or an equation like $0=1$ .
Induction Hypothesis: The induction hypothesis is the temporary assumption that $P(k)$ , or several earlier statements, are true during the induction step.
Counterexample: A counterexample is one specific value or object that makes a universal statement $\forall x,\ P(x)$ false.
Uniqueness: Uniqueness means that at most one object satisfies a property, often proved by showing $P(a) \land P(b) \Rightarrow a=b$ .

Common Mistakes to Avoid

Assuming the conclusion in a direct proof is circular reasoning because it uses $Q$ before proving that $P \Rightarrow Q$ is valid.
Proving the converse instead of the original statement is wrong because $Q \Rightarrow P$ is not logically equivalent to $P \Rightarrow Q$ .
Skipping the base case in induction is invalid because the induction step only transfers truth from one case to the next and does not start the chain.
Using a non-exhaustive case split is incomplete because the proof may ignore elements of the domain where the statement could fail.
Giving an example for a universal statement is insufficient because showing $P(a)$ for one value does not prove $\forall x \in S,\ P(x)$ .

Practice Questions

1 Prove directly that if $n$ is an even integer, then $n^2$ is even.
2 Use contrapositive proof to show that if $n^2$ is odd, then $n$ is odd.
3 Use induction to prove that $1+2+\cdots+n=\frac{n(n+1)}{2}$ for every integer $n \geq 1$ .
4 For the claim $\forall x \in \mathbb{R},\ x^2 \geq x$ , decide whether to prove it or disprove it, and explain which proof technique is appropriate.

Understanding Mathematical Proof Techniques College Reference

Proof writing begins with precise meanings. Before choosing a method, unpack every definition in the claim. For example, proving that an integer is even means showing it can be written as two times some integer.

The unknown integer must be named and its required properties must be stated. Quantifiers tell you what kind of work is needed. A statement about every object requires a general argument that works for an arbitrary object.

A statement claiming that some object exists needs one valid example or a reason one must occur. Many proof errors come from treating a chosen example as if it represented every possible case.

The shape of a statement often suggests the best route. Direct reasoning is useful when the assumption gives material that can be rewritten using definitions. A contrapositive approach is often shorter when the conclusion is difficult to handle but its failure has clear consequences.

For instance, claims about divisibility, parity, or nonzero values often become simpler when working backward from what would prevent the conclusion. Contradiction is valuable when an assumption forces two incompatible facts, but the contradiction must follow from valid steps rather than from an unstated belief. In casework, the cases must cover every possibility and must not quietly leave out boundary values.

Induction is more than checking a pattern for several numbers. The induction step must explain how a later case is forced by earlier information. It is important to state exactly what may be assumed during that step.

In ordinary induction, only one preceding case is available. In strong induction, all earlier cases in the stated range are available. Strong induction is common when an object can be broken into smaller pieces, such as factoring an integer or analyzing a recursive algorithm.

Base cases matter because they start the chain. If a formula begins at a particular number, proving a different starting case does not fix the gap.

Existence and uniqueness require different kinds of evidence. A construction proof should verify that the object created really has every required property. It is not enough to name a familiar object and move on.

An indirect existence proof may use a counting argument, a completeness property, or contradiction. For uniqueness, compare two arbitrary candidates that both satisfy the condition and use the condition to show they cannot differ. Counterexamples are equally important because they test whether a claim is too broad.

One example only defeats a claim about every object. It does not defeat a claim about some object. In courses, these habits appear when checking computer algorithms, proving rules for matrices, studying limits, and deciding whether a proposed theorem needs extra assumptions.

Sign in to save

Sign in to save

Mathematical Proof Techniques College Reference Cheat Sheet

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Key Facts

Vocabulary

Common Mistakes to Avoid

Practice Questions

Understanding Mathematical Proof Techniques College Reference