Day 28 — Direct proof

Day 28 — Direct proof

Stage III · concept day
Goal: Structure a direct proof of \(P\rightarrow Q\); prove even/odd and divisibility claims; unpack definitions; prove biconditionals in both directions; choose definitions that make the algebra work.

Why this matters

Direct proof is the default tool: assume the hypothesis, unfold definitions, chain equalities/implications, conclude the goal. Most correctness arguments for arithmetic properties, invariant maintenance steps, and “if pre then post” lemmas are direct. Without a clean template, write-ups ramble and hide gaps.

Theory

What a proof is (working contract)

A proof is a finite sequence of statements, each a premise, a definition, a logical consequence of earlier statements, or a cited theorem, ending at the claim. Audience: a competent peer who may challenge any unjustified leap.

Direct proof of \(P \rightarrow Q\)

Template:

1. State the claim clearly (quantifiers explicit).
   
2. Assume \(P\) (for arbitrary objects named in \(\forall\)).
   
3. Unpack definitions in \(P\).
   
4. Reason with algebra, known theorems, earlier lemmas.
   
5. Pack the definition of \(Q\).
   
6. Conclude \(Q\), hence \(P\rightarrow Q\). Discharge the assumption.

For \(\forall x\,(P(x)\rightarrow Q(x))\): fix arbitrary \(x\), assume \(P(x)\), prove \(Q(x)\).

Definitions to own (parity)

Let \(n\in\mathbb{Z}\).

• \(n\) is even iff \(\exists k\in\mathbb{Z}\, (n = 2k)\).
  
• \(n\) is odd iff \(\exists k\in\mathbb{Z}\, (n = 2k+1)\).

These are existentially packed. Direct proofs often: assume even, choose a witness \(k\), manipulate, exhibit a witness for the conclusion.

Definitions to own (divisibility)

For \(a,b\in\mathbb{Z}\), \(a \mid b\) (“\(a\) divides \(b\)”) iff \(\exists m\in\mathbb{Z}\, (b = a m)\).
\(a\) is a divisor of \(b\); \(b\) is a multiple of \(a\).

Choosing good definitions

Equivalent definitions must be used consistently. Prefer the form that matches the algebra:

• Even as \(2k\) helps products and sums.
  
• Sometimes \(n \equiv 0 \pmod{2}\) (Day 5/73 family) is cleaner for modular reasoning—same idea.

Biconditional proofs

To prove \(P \leftrightarrow Q\), prove both:

1. \(P \rightarrow Q\) (⇒ direction),
   
2. \(Q \rightarrow P\) (⇐ direction).

Label directions. Do not assume both at once.

“If and only if” via chain

Sometimes \(P \Leftrightarrow Q \Leftrightarrow R\) by a chain of equivalences (each step iff). Valid when every step is reversible. One-directional chains only prove one arrow.

Common direct-proof patterns

Pattern	Skeleton
Parity of sum/product	Expand \(2k\), \(2m+1\) forms
Divisibility preserve	\(b=am\), \(c=an\) ⇒ linear combo
Equality of numbers	Transform expression
Subset-style (later)	element chase
From inequality hyp	algebraic rearrangement with justified steps

What direct proof is not

• Not proof by example (“true for \(n=3\)”).
  
• Not proof by converse (proving \(Q\rightarrow P\) when you needed \(P\rightarrow Q\)).
  
• Not assuming \(Q\) mid-stream without derivation.

Quantifiers in the write-up

• Arbitrary but fixed: “Let \(n\) be an arbitrary even integer.”
  
• Witnesses: “So \(n=2k\) for some \(k\in\mathbb{Z}\).”
  
• Exhibit: “Thus \(n^2 = 2(2k^2)\), so \(n^2\) is even with witness \(2k^2\).”

Lemmas and structure

Factor repeated algebra as a lemma (e.g. product of evens is even) and cite it. Large proofs are trees of direct lemmas.

Worked examples

Example 1 — Even square

Claim. If \(n\) is even, then \(n^2\) is even.

Proof. Assume \(n\) even. Then \(n=2k\) for some \(k\in\mathbb{Z}\).
\(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\).
So \(n^2 = 2\cdot m\) with \(m=2k^2\in\mathbb{Z}\). Hence \(n^2\) is even. \(\square\)

Example 2 — Odd square

Claim. If \(n\) is odd, then \(n^2\) is odd.

Proof. \(n=2k+1\) ⇒ \(n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1\), odd. \(\square\)

Example 3 — Sum of evens

Claim. If \(a,b\) even then \(a+b\) even.

Proof. \(a=2k\), \(b=2m\) ⇒ \(a+b=2(k+m)\). \(\square\)

Example 4 — Divisibility transitive

Claim. If \(a\mid b\) and \(b\mid c\) then \(a\mid c\).

Proof. \(b=as\), \(c=bt\) for some \(s,t\in\mathbb{Z}\).
\(c = (as)t = a(st)\), so \(a\mid c\). \(\square\)

Example 5 — Linear combination

Claim. If \(a\mid b\) and \(a\mid c\) then \(a\mid (bx+cy)\) for all \(x,y\in\mathbb{Z}\).

Proof. \(b=am\), \(c=an\) ⇒ \(bx+cy = a(mx+ny)\). \(\square\)

Example 6 — Biconditional parity

Claim. \(n\) even iff \(n^2\) even. (One direction Example 1; converse often by contrapositive Day 29—or cases.)

Direct-ish converse via cases: if \(n\) odd then \(n^2\) odd (Ex. 2), so if \(n^2\) even, \(n\) cannot be odd, hence even (law of excluded middle on parity). Full case hygiene is Day 30.

Example 7 — If divides then divides square

Claim. If \(a\mid b\) then \(a\mid b^2\).

Proof. \(b=ak\) ⇒ \(b^2 = a^2 k^2 = a(ak^2)\). \(\square\)

Example 8 — Unpack carefully

Claim. If \(n\mid m\) and \(n>0\), \(m>0\), then \(n \le m\).

Proof. \(m = nq\) with \(q\in\mathbb{Z}\). Since \(m>0\), \(n>0\), must have \(q \ge 1\) (if \(q\le 0\) then \(m\le 0\)). Thus \(m = nq \ge n\cdot 1 = n\). \(\square\)

Example 9 — Algebraic identity as direct proof

Claim. For all \(n\in\mathbb{Z}\), \((n+1)^2 - n^2 = 2n+1\).

Proof. Expand left: \(n^2+2n+1-n^2=2n+1\). \(\square\)
(Universal claim proved by arbitrary \(n\) and algebra.)

Example 10 — Product of odds

Claim. If \(a,b\) odd then \(ab\) odd.

Proof. \(a=2k+1\), \(b=2m+1\) ⇒ \(ab = 4km+2k+2m+1 = 2(\cdots)+1\). \(\square\)

Example 11 — Spec style

Claim. If a buffer’s size \(n\) is even and we split into two equal halves, each half has integer length \(n/2\).

Proof. \(n=2k\) ⇒ half length \(k\in\mathbb{Z}\). \(\square\)
(Trivial but matches how systems proofs start.)

Example 12 — Two directions labeled

Claim. For \(n\in\mathbb{Z}\), \(3\mid n\) iff \(3\mid 2n\) is false as biconditional? Check: if \(3\mid n\) then \(3\mid 2n\) (direct). Converse: \(3\mid 2n\) does not imply \(3\mid n\) (counterexample \(n=1\) fails \(3\mid 2\); actually \(n=3\) works both. Counterexample for converse: need \(3\mid 2n\) but not \(3\mid n\). Since \(3\) prime, \(3\mid 2n\) ⇒ \(3\mid n\). So on integers with Euclid’s lemma it holds—use Day 71+ or accept via prime property. Alternative claim: \(4\mid 2n\) not iff \(4\mid n\) (\(n=2\): \(4\mid 4\) but \(4\nmid 2\)). Use that.

Claim. \(4\mid 2n\) does not imply \(4\mid n\). Counterexample \(n=2\). Direct proof of ⇒ for \(2\mid n \Rightarrow 4\mid 2n\)? If \(n=2k\), \(2n=4k\). Yes.

Example 13 — From hypothesis equality

If \(a=b\), then \(a+c=b+c\) (add same to both sides)—direct from properties of equality (substitution).

Example 14 — Rational closed under multiplication (sketch)

If \(x=p/q\), \(y=r/s\) with \(q,s\neq 0\), then \(xy = (pr)/(qs)\) with \(qs\neq 0\). Direct from definition of \(\mathbb{Q}\).

Exercises

Write full proofs. Quantify variables.

1. If \(n\) is even, then \(n+2\) is even.
   
2. If \(n\) is odd, then \(n+1\) is even.
   
3. If \(a\mid b\) and \(a\mid c\), then \(a\mid (b+c)\).
   
4. If \(a\mid b\), then \(a\mid (-b)\).
   
5. If \(n\) is even, then \(3n\) is even.
   
6. If \(a\) and \(b\) are even, then \(ab\) is even.
   
7. Prove: for all \(n\in\mathbb{Z}\), \(n(n+1)\) is even. (Hint: cases on parity—or note consecutive.)
   
8. If \(5\mid n\), then \(5\mid n^2\).
   
9. Prove transitivity of \(\mid\) again in your own words.
   
10. If \(a\mid b\) and \(b\neq 0\), then \(|a| \le |b|\). (Careful with negatives.)
    
11. Prove: \(n\) odd iff \(n=2k+1\) for some \(k\)—if this is your definition, instead prove \(n\) odd iff \(n-1\) even.
    
12. Show if \(a\mid b\) and \(a\mid c\) then \(a^2 \mid bc\) need not hold? Or prove \(a\mid b \Rightarrow a^2 \mid b^2\).
    
13. Prove \((n+1)^3 - n^3 = 3n^2+3n+1\) by expansion.
    
14. If \(x\) and \(y\) are rational, \(x+y\) is rational (direct from definitions).
    
15. Prove: if \(n\mid m\) and \(m\mid n\) then \(|n|=|m|\) for integers.
    
16. Biconditional: \(n\) even iff \(n+1\) odd. Both directions.
    
17. If \(a\mid b\) and \(c\mid d\) then \(ac\mid bd\).
    
18. Disprove by counterexample: if \(a\mid bc\) then \(a\mid b\) or \(a\mid c\).
    
19. Prove: sum of an even and an odd is odd.
    
20. Write a direct proof that for all \(n\ge 1\), the number of edges in a path of \(n\) nodes is \(n-1\) (define path graph cleanly in one sentence).
    
21. If \(2\mid n\) and \(3\mid n\) then \(6\mid n\) (may use \(\mathrm{lcm}\) or explicit \(n=2a=3b\) and solve—or wait for number theory; try \(n=6k\) construction from Bézout awareness).
    
22. Prove: if \(n=2k\) then \(n^2 \equiv 0 \pmod 4\).
    
23. Direct proof from definition: \(\forall n\in\mathbb{Z}\, (n \le n)\).
    
24. Prove if \(A\subseteq B\) and \(B\subseteq C\) then \(A\subseteq C\) (element chase—sets Day 35 preview).
    
25. State and prove a small lemma you invent about odd integers (e.g. difference of odds is even).

CS connection

• Spec lemmas: if request is authorized (\(P\)), then status is not \(401\) (\(Q\))—direct from auth module definition.
  
• Invariant step: assume invariant holds before iteration, show after—direct proof body (Day 32).
  
• Parity bits and alignment: “if size even then can pair bytes” is Example 11-shaped.
  
• Divisibility in paging / blocks: block size divides segment length.
  
• Proof reviews: demand unpacked definitions the same way code reviews demand unpacked invariants.
  
• Automated provers still need human-structured direct lemmas for readable assurance cases.

Common pitfalls

Pitfall	What to do instead
Proof by example	Arbitrary \(n\), not \(n=4\)
Assuming the conclusion	Assume only \(P\)
Forgetting to exhibit witnesses	Produce \(k\) explicitly
Circular use of the claim	Only prior lemmas/definitions
One direction for iff	Prove both ⇒ and ⇐
Hidden quantifier on \(k\)	“for some \(k\in\mathbb{Z}\)”
Division by zero in rational proofs	Track denominators \(\neq 0\)
Using “clearly” for a multi-step gap	Write the steps

Checkpoint

• Write the direct-proof template from memory
  
• Prove even ⇒ even square without notes
  
• Prove a divisibility claim with witnesses
  
• Complete one full biconditional
  
• Spot a proof-by-example fallacy
  
• Unpack at least two definitions in a proof
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — definition hygiene

Every direct proof is only as good as its definitions. Before writing:

1. Write the claim with quantifiers.
   
2. Expand every keyword (even, divides, rational, subset, …).
   
3. Note what a witness looks like for existential parts of the hypothesis.
   
4. Note what witness you must build for the conclusion.

Parity closed-form toolkit

Object	Algebraic form
Even \(n\)	\(2k\)
Odd \(n\)	\(2k+1\)
Even + even	even
Odd + odd	even
Even + odd	odd
Even \(\times\) anything	even
Odd \(\times\) odd	odd

Prove each once; cite thereafter.

Divisibility toolkit

• \(a\mid a\), \(a\mid 0\), \(1\mid a\) for all \(a\).
  
• If \(a\mid b\) and \(b\mid c\) then \(a\mid c\).
  
• If \(a\mid b\) and \(a\mid c\) then \(a\mid (bx+cy)\).
  
• If \(a\mid b\) and \(b\neq 0\) then \(|a|\le|b|\).

More worked examples

Example 15 — Difference of squares
If \(n\) odd then \(n^2-1\) divisible by \(8\): \(n=2k+1\), \(n^2-1=4k(k+1)\) and \(k(k+1)\) even so extra factor \(2\).

Example 16 — Rational sum
Direct from \(p/q+r/s=(ps+qr)/(qs)\).

Example 17 — Spec lemma
If buffer length \(n\) divisible by \(4\), then number of 4-byte words is \(n/4\in\mathbb{Z}\).

Example 18 — Biconditional trap
\(2\mid n\) iff \(2\mid n^2\) is true (both directions)—prove carefully; do not assume the converse of a random divisibility.

Additional exercises

26. Prove: if \(n\) odd then \(n^2\equiv 1\pmod 8\).
    
27. Prove: \(a\mid b\) iff \(a\mid -b\).
    
28. Prove both directions: \(n\) odd iff \(n^2\) odd.
    
29. If \(3\mid n\) and \(3\mid m\) then \(3\mid (n^2+m^2)\)—direct.
    
30. Write a graded rubric: what must appear in a full direct proof of “even \(\Rightarrow\) even square.”

Extended practice workshop

Parity proofs (full write-ups)

1. Even + even = even
   
2. Odd + odd = even
   
3. Even + odd = odd
   
4. Even × anything = even
   
5. Odd × odd = odd
   
6. Even ⇒ even square
   
7. Odd ⇒ odd square
   
8. \(n(n+1)\) always even

Divisibility proofs

9. Transitivity of \(\mid\)
   
10. Linear combination closure
    
11. \(a\mid b \Rightarrow a\mid b^2\)
    
12. \(a\mid b\) and \(b\neq 0\) ⇒ \(|a|\le|b|\) (careful signs)
    
13. \(a\mid b\) and \(b\mid a\) ⇒ \(|a|=|b|\)

Biconditionals

14. \(n\) even iff \(n+1\) odd
    
15. \(n\) odd iff \(n^2\) odd

Spec-shaped

16. If block size divides segment length, segment is whole number of blocks.
    
17. If \(n\) divisible by \(4\), half of half is integer.

Meta

18. Unpack “rational” in a sum-of-rationals proof.
    
19. Rubric a peer’s proof of even square.
    
20. Spot proof-by-example fallacy in a fake write-up.

Direct proof pocket card

Assume P (arbitrary objects)
Unpack definitions
Algebra / known lemmas
Pack definition of Q
Conclude P → Q

Tomorrow

Day 29 — Contrapositive & contradiction. When to switch methods; \(\sqrt{2}\) irrational; infinite primes recall; uniqueness via contradiction.