Number & Algebra

A valid step-by-step argument that establishes the truth of a mathematical statement. Examples DON'T constitute proof — they merely suggest.

Cautionary: $f(n)=n^2+n+41$ gives primes for $n = 0, \dots, 39$ — then fails at $n=40$ where $f(40)=41^2$. Patterns that hold for many cases can still be false.

Start from what's given; use algebra + known facts; reach the conclusion in steps with no leaps. Mark the end with $\blacksquare$.

Sum of two evens is even. Template: 'Let $m, n \in \mathbb{Z}$. Then $2m, 2n$ are even. Their sum is $2(m+n) \in 2\mathbb{Z}$. $\blacksquare$'

Building blocks for nearly every algebraic direct proof.

Used constantly in number-theory proofs.

To disprove a 'for all' statement. ONE failing case is enough; no need to find more.

'Every prime is odd' — counterexample: $n=2$ is prime AND even. Claim disproved.

Counterexamples DISPROVE universal claims only. They can't disprove existence claims like 'there exists $x$ with …'.

(1) Assume the negation of the statement. (2) Derive a logical impossibility or contradiction with known fact. (3) Conclude the original must be true. $\blacksquare$

Assume $\sqrt 2 = p/q$ in lowest terms. Square: $p^2 = 2q^2 \Rightarrow p$ even. Then $4k^2 = 2q^2 \Rightarrow q$ also even. But $p, q$ share factor 2 — contradicts 'lowest terms'.

Assume primes finite: $p_1, \dots, p_n$. Let $N = p_1 p_2 \cdots p_n + 1$. Then $N$ has a prime divisor distinct from all $p_i$ — contradiction.

(1) Base case: show $P(1)$ (or $P(n_0)$ where the claim starts). (2) Inductive step: assume $P(k)$, prove $P(k+1)$. Conclude $P(n)$ for all $n \ge n_0$. $\blacksquare$

Base case knocks the first domino. Inductive step says each falling domino knocks the next. Conclude: all fall. Both parts essential — omit either and the chain breaks.

The assumed statement $P(k)$. To bridge to $P(k+1)$: add the $(k+1)$-th term to both sides (for sums), or multiply both sides by the relevant factor.

Base: $1 = 1\cdot2/2$ ✓. Step: add $(k+1)$ to IH ⇒ $\tfrac{k(k+1)}{2} + (k+1) = \tfrac{(k+1)(k+2)}{2}$ ✓.

Prove $2^n > n^2$ for $n \ge 5$. Base $n=5$: $32 > 25$ ✓. Step: $2^{k+1} = 2\cdot 2^k > 2k^2 \ge (k+1)^2$ since $2k^2-(k+1)^2 = k^2-2k-1 > 0$ for $k \ge 5$.

'For all $n \in \mathbb{Z}^+$' → induction. 'For all $x \in \mathbb{R}$, $P$' → direct proof. 'For all …' suspected false → counterexample. 'No such $x$' or '$x$ is irrational' → contradiction.

You MUST use the inductive hypothesis $P(k)$ inside the proof of $P(k+1)$. If the hypothesis is never invoked, your 'proof' isn't induction — it's just direct.

Make sure the negation is fully derived to a CONTRADICTION (e.g. '$a$ both even and odd', '$0 = 1$'). Just 'this doesn't look right' is not enough.

A single example does NOT prove a 'for all' claim — it only suggests. Don't try to 'prove' by finding one positive case.