Mathematical Proofs (Direct, Contradiction, Induction) Cheat Sheet

Key Facts

• A direct proof starts with the given information and uses definitions, algebra, and known facts to reach the conclusion.
• To prove a conditional statement directly, assume $P$ is true and show that $Q$ must be true for the statement $P \Rightarrow Q$.
• A proof by contradiction assumes the negation of the conclusion, then shows that this assumption leads to an impossible statement such as $0 = 1$.
• The contradiction method proves $P$ by assuming $\neg P$ and deriving both $R$ and $\neg R$, which cannot both be true.
• A mathematical induction proof has a base case, usually $n = 1$ or $n = 0$, and an inductive step from $n = k$ to $n = k + 1$.
• In induction, the induction hypothesis assumes the statement is true for $n = k$, and the goal is to prove it true for $n = k + 1$.
• A common induction template is: prove $P(1)$, assume $P(k)$, prove $P(k + 1)$, then conclude $P(n)$ is true for all integers $n \ge 1$.
• To disprove a universal statement such as $\forall n, P(n)$, it is enough to find one counterexample where $P(n)$ is false.

Vocabulary

Direct proof

A proof method that begins with known facts or assumptions and logically derives the desired conclusion.

Contradiction

A proof method that assumes the opposite of what must be proven and shows that this assumption creates an impossibility.

Mathematical induction

A proof method used to prove statements about integers by proving a starting case and a repeating step.

Base case

The first value in an induction proof, such as $n = 1$, that must be verified directly.

Induction hypothesis

The temporary assumption in an induction proof that the statement is true for $n = k$.

Counterexample

A single example that proves a universal statement is false.