In geometry you wrote two-column proofs: each line a fact, each fact justified. A direct proof in discrete math is the same idea written as sentences. It chains valid steps (modus ponens, over and over), and unlike a list of examples it covers every case at once.
Key idea
To prove "if $P$, then $Q$" directly: assume $P$, rewrite it using definitions, and reason step by step until you reach $Q$. Definitions turn words into algebra: $n$ is even when $n = 2k$ for some integer $k$; $n$ is odd when $n = 2k + 1$ for some integer $k$; $a$ divides $b$, written $a \mid b$, when $b = ak$ for some integer $k$.
Why it works
Writing an odd number as $2k + 1$ with $k$ unknown is what makes the proof general. Every odd number has that form, so an argument that only uses the form works for all of them at once. An example like $n = 7$ uses the specific number $7$ and says nothing about $9$ or $1001$. The letter $k$ is a stand-in for "whatever it happens to be."
Worked examples
Worked example: The product of two odd numbers is odd
Prove: if $m$ and $n$ are odd, then $mn$ is odd.
- Assume $m$ and $n$ are odd. Then $m = 2a + 1$ and $n = 2b + 1$ for some integers $a$ and $b$. (Two letters, because $m$ and $n$ may be different.)
- Multiply: $mn = (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1$.
- Factor $2$ from the first three terms: $mn = 2(2ab + a + b) + 1$.
- $2ab + a + b$ is an integer, so $mn$ has the form $2k + 1$: it is odd.
Answer: $mn = 2(2ab + a + b) + 1$, which is odd.
Worked example: Divisibility is transitive
Prove: if $a \mid b$ and $b \mid c$, then $a \mid c$.
- Assume $a \mid b$ and $b \mid c$. By definition, $b = ak$ and $c = bj$ for some integers $k$ and $j$.
- Substitute: $c = bj = (ak)j = a(kj)$.
- $kj$ is an integer, so $c$ is $a$ times an integer: $a \mid c$.
Answer: $c = a(kj)$, so $a \mid c$.
Worked example: A remainder pattern
Prove: if $n$ is odd, then $n^{2} - 1$ is a multiple of $4$.
- Assume $n$ is odd: $n = 2k + 1$.
- Then $n^{2} - 1 = 4k^{2} + 4k + 1 - 1 = 4(k^{2} + k)$.
- $k^{2} + k$ is an integer, so $n^{2} - 1$ is a multiple of $4$. (With one more idea, that $k^{2} + k = k(k + 1)$ is even, you can show it is a multiple of $8$.)
Answer: $n^{2} - 1 = 4(k^{2} + k)$
Common mistake
Checking numbers, or reusing a letter. "$3 \cdot 5 = 15$ and $7 \cdot 9 = 63$ are odd" is evidence, not a proof. And writing two even numbers as $2k$ and $2k$ quietly assumes they are equal: the "proof" that the sum of two evens is a multiple of $4$ ($2k + 2k = 4k$) fails for $2 + 4 = 6$. Check: each new number gets its own letter, and every step must hold for every value of the letters.