Writing It Up

Study Sheet

Writing It Up

How a proof should read on the page

Style Rules

Concept
The reader's rules

Write in full sentences. State what you are proving and what you assume. Name every variable before using it ("let kk be an integer such that…"). Give the method up front ("we proceed by induction on nn"). Justify each step with a reason a skeptical reader accepts. End with what has been shown, and mark it: ■\blacksquare or "which completes the proof".

A proof is written for someone who is trying to find a mistake. Assume that reader is intelligent, careful, and unwilling to guess what you meant. Symbols save space but hide gaps: a page of equal signs with no words is usually a page of unjustified steps. The right proportion is about half words, half mathematics, and the words carry the logic — "so", "because", "suppose", "therefore", "for all".

Tip
Words that do work

"Suppose", "let", "since", "therefore", "it follows that", "in particular", "conversely", "without loss of generality" (say why), "by the inductive hypothesis". Avoid "obviously", "clearly", and "it is easy to see" — if it is, show it in a line; if it is not, the word is hiding the gap.

Example
Before and after

Draft: "nn odd →\to n=2k+1n = 2k+1 →\to n2=4k2+4k+1n^2 = 4k^2 + 4k + 1 →\to odd." Final: "Let nn be odd, so n=2k+1n = 2k + 1 for some integer kk. Then n2=4k2+4k+1=2(2k2+2k)+1n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, which is odd since 2k2+2k2k^2 + 2k is an integer. ■\blacksquare" Same mathematics; the second can be checked.

Example
Before and after: an induction

Draft: "n=0n = 0 ok. 3n+1=3⋅3n≥3(2n+1)≥2n+33^{n+1} = 3\cdot3^n \ge 3(2n + 1) \ge 2n + 3." Final: "We prove 3n≥2n+13^n \ge 2n + 1 for all n≥0n \ge 0 by induction on nn. For n=0n = 0, 30=1=2⋅0+13^0 = 1 = 2\cdot0 + 1. Suppose 3k≥2k+13^k \ge 2k + 1 for some k≥0k \ge 0. Then 3k+1=3⋅3k≥3(2k+1)=6k+3≥2k+3=2(k+1)+13^{k+1} = 3\cdot3^k \ge 3(2k + 1) = 6k + 3 \ge 2k + 3 = 2(k + 1) + 1, where the last inequality uses k≥0k \ge 0. This is the claim for k+1k + 1, which completes the induction. ■\blacksquare" The final version names the method, the hypothesis, the target, and the one place k≥0k \ge 0 is used.

Side note
Where it goes wrong

Arrows (⇒\Rightarrow) used as sentence connectors, unquantified variables ("x2≥0x^2 \ge 0" — for which xx?), and a proof that ends in mid-computation without stating the conclusion.

Try it
Try it: rewrite

Rewrite as a proof: "a∣ba \mid b, b=akb = ak, a∣bca \mid bc since bc=a(kc)bc = a(kc)."

Show the answer

"Suppose a∣ba \mid b. Then b=akb = ak for some integer kk. For any integer cc, bc=(ak)c=a(kc)bc = (ak)c = a(kc), and kckc is an integer, so a∣bca \mid bc. ■\blacksquare"

Checking Your Own Proof

Concept
The audit

Before calling a proof finished: (1) Did you use every hypothesis? (2) Did you handle every case, including degenerate ones (n=0n = 0, empty set, equal points)? (3) Does each step follow from the ones before, not from the conclusion? (4) Would the argument also "prove" something false? — if so, it is wrong. (5) Does the last line say exactly what was claimed?

Question (4) is the most powerful and the least used. Change one hypothesis so that the theorem becomes false, and read your proof again: some line must now fail. If none does, the proof never used that hypothesis — and a proof that survives without a hypothesis the theorem needs is broken somewhere.

Example
Test 1 in action: every hypothesis used

Claim: if pp is a prime greater than 33, then 24∣p2−124 \mid p^2 - 1. Because the claim fails for p=3p = 3 (32−1=83^2 - 1 = 8), a correct proof must use p>3p > 3 somewhere. It does, twice. Since p≠2p \ne 2, pp is odd, so 8∣p2−18 \mid p^2 - 1 (odd squares leave remainder 11 mod 88). Since p≠3p \ne 3, 3∤p3 \nmid p, so pp leaves remainder 11 or 22 mod 33 and p2p^2 leaves remainder 11: 3∣p2−13 \mid p^2 - 1. As gcd⁡(8,3)=1\gcd(8, 3) = 1, 24∣p2−124 \mid p^2 - 1. ■\blacksquare

Example
Test 4 in action

"Proof" that 1=21 = 2: let a=ba = b; a2=aba^2 = ab; a2−b2=ab−b2a^2 - b^2 = ab - b^2; (a−b)(a+b)=b(a−b)(a - b)(a + b) = b(a - b); a+b=ba + b = b; 2b=b2b = b; 2=12 = 1. The argument proves something false, so a step is wrong: dividing by a−b=0a - b = 0. Every proof that divides must say why the divisor is nonzero.

Side note
Where it goes wrong

Auditing the algebra and not the logic. Every line of the "1=21 = 2" proof is correct algebra except for one hidden division; every line of the horses proof is correct except for one value of kk. Errors hide in the steps that feel too routine to check.

Try it
Try it: audit

Audit: "Every positive integer is interesting. Suppose not; let nn be the smallest uninteresting integer. But being the smallest uninteresting integer is interesting — contradiction." What is wrong?

Show the answer

"Interesting" is not a mathematical property with a definition; the proof uses the word in two different senses. A proof about a set needs the set to be well-defined. (The pattern — smallest counterexample, then contradiction — is a valid one; the object is the problem.)

Structuring a Longer Proof

Concept
Lemmas, cases, and "without loss of generality"

Split a long proof into a lemma (a smaller claim proved first and then used) and the main argument. Label cases and say why they are exhaustive. Write "without loss of generality" (WLOG) only when the cases you skip are the same as the one you do up to a symmetry — and name the symmetry.

Structure is for the reader. A lemma lets the reader check one idea at a time and lets you reuse it; labelled cases let the reader tick them off; a WLOG saves writing the same argument twice. Each is an honest shortcut only if the reader can see it is honest, which is why every WLOG needs its reason: "since the statement is symmetric in xx and yy".

Example
WLOG done right

Claim: for real x,yx, y, ∣x−y∣=max⁡(x,y)−min⁡(x,y)|x - y| = \max(x, y) - \min(x, y). Both sides are unchanged when xx and yy are swapped, so without loss of generality x≥yx \ge y. Then x−y≥0x - y \ge 0, so ∣x−y∣=x−y|x - y| = x - y; and max⁡(x,y)=x\max(x, y) = x, min⁡(x,y)=y\min(x, y) = y. The two sides agree. ■\blacksquare

Example
A lemma first

Claim: the product of any three consecutive integers is divisible by 66. Lemma. Among any kk consecutive integers, one is divisible by kk. (Their remainders mod kk are kk consecutive values, so every remainder appears once, including 00.) Proof of the claim. By the lemma with k=2k = 2 and k=3k = 3, the product has a factor divisible by 22 and a factor divisible by 33. So 22 and 33 both divide it, and since gcd⁡(2,3)=1\gcd(2, 3) = 1, so does 66. ■\blacksquare

Side note
Where it goes wrong

A WLOG that is not symmetric. To prove a−b≤∣a−b∣a - b \le |a - b|, "WLOG a≥ba \ge b" skips the case a<ba < b, and the statement is NOT symmetric in aa and bb (swapping them changes the left side). That case needs its own line: there a−b<0≤∣a−b∣a - b < 0 \le |a - b|.

Try it
Try it: structure it

Prove that the product of any four consecutive integers is divisible by 2424.

Show the answer

Among four consecutive integers two are even, and they are consecutive even numbers, so one of them is divisible by 44: the product has a factor 22 and a different factor 44, so 88 divides it. By the lemma with k=3k = 3, one of the four is divisible by 33. Since gcd⁡(8,3)=1\gcd(8, 3) = 1, 2424 divides the product. ■\blacksquare

Putting It Together

Claim: for every positive integer nn, 3∣n3+2n3 \mid n^3 + 2n.

Draft. "n=1n = 1: 33. n=2n = 2: 1212. n=3n = 3: 3333. n3+2n=n(n2+2)n^3 + 2n = n(n^2 + 2). If 3∣n3 \mid n done. Otherwise n2+2≡0n^2 + 2 \equiv 0. So always." Flaws: the examples prove nothing; "≡0\equiv 0" is asserted with no modulus and no reason; the cases are not named or shown to be exhaustive; the last line does not state the claim.

Final. "Let nn be a positive integer. We consider its remainder on division by 33. If n=3kn = 3k, then n3+2n=n(n2+2)n^3 + 2n = n(n^2 + 2) has the factor nn, divisible by 33. If n=3k±1n = 3k \pm 1, then n2=9k2±6k+1n^2 = 9k^2 \pm 6k + 1, so n2+2=3(3k2±2k+1)n^2 + 2 = 3(3k^2 \pm 2k + 1) is divisible by 33, and so is n(n2+2)n(n^2 + 2). These cases cover every integer, so 3∣n3+2n3 \mid n^3 + 2n for every positive integer nn. ■\blacksquare"

Example
Look back: a second proof

The same claim, differently: n3+2n=(n3−n)+3n=(n−1)n(n+1)+3nn^3 + 2n = (n^3 - n) + 3n = (n - 1)n(n + 1) + 3n. The first term is a product of three consecutive integers, divisible by 33 by the lemma of the previous section, and the second is a multiple of 33. ■\blacksquare Finding a second proof is the "look back" step, and here it shows the real reason: n3+2nn^3 + 2n differs from a product of consecutive integers by a multiple of 33.

Tip
The final read

Read the finished proof once as its harshest reader: cover each line, ask what the previous lines force, and uncover. Every "clearly" gets a reason or is deleted. Every variable was introduced before it appears. The last sentence states the claim exactly as it was given.