M5 · Lesson 5 — Mathematical Reasoning

Writing Your
First Proof

Reading proofs builds recognition. Writing them builds
genuine mathematical confidence.

01
M5 · L5 — The Structure

Every proof has the same skeleton

The anatomy of
a written proof

  • Statement — "We prove that..." or "Theorem: ..."
  • Proof declaration — "Proof." (literally this word, followed by a period)
  • Argument — your logical steps, clearly numbered or sequenced
  • Conclusion — "Therefore..." restating what was proved
  • QED marker — □ or ■ at the end

The □ (tombstone) matters. It signals exactly where the proof ends. Without it, readers don't know if they've reached the conclusion or an intermediate step.

# Standard proof skeleton Theorem. [statement of what you're proving] Proof. Let [introduce variables]. By assumption, [invoke hypotheses]. [logical steps] It follows that [intermediate result]. Therefore, [conclusion]. □
02
M5 · L5 — Phrase Library

The standard vocabulary

Proof phrases you
need to know

Introducing variables
"Let u ∈ 𝒰 be an arbitrary user..."
Invoking assumptions
"By assumption / By hypothesis..."
Using a known result
"By Lemma 1 / By the chain rule..."
Stating a consequence
"It follows that / We obtain..."
Without loss of generality
"WLOG, assume i > j..."
Contradiction
"Suppose for contradiction that..."
Concluding
"Therefore / Hence / Thus..."
End of proof
"This completes the proof. □"
03
M5 · L5 — Worked Example

A complete RS proof

Proving non-negativity
of the regularised MF loss

Proposition. The regularised MF loss ℒ = ∑_{(u,i)∈𝒪}(r_{ui} − p_u^⊤q_i)² + λ(‖P‖²_F + ‖Q‖²_F) satisfies ℒ ≥ 0 for all P, Q and λ > 0.
Proof. Let P ∈ ℝ^{m×d} and Q ∈ ℝ^{n×d} be arbitrary embedding matrices and let λ > 0.

For any (u,i) ∈ 𝒪, the squared error (r_{ui} − p_u^⊤q_i)² ≥ 0 since it is a square of a real number.

By assumption λ > 0 and ‖P‖²_F, ‖Q‖²_F ≥ 0 as squared norms, hence λ(‖P‖²_F + ‖Q‖²_F) ≥ 0.

Therefore ℒ is a sum of non-negative terms, so ℒ ≥ 0. □
■

Anatomy of this proof:

  • Opens with "Let" — introduces variables precisely
  • "By assumption" — invokes the hypothesis λ > 0
  • Each inequality justified — squared values, positive λ
  • "Therefore" — signals the conclusion
  • □ marks the end cleanly

Notice: This proof is short. Good proofs are as short as possible — not as long as possible. Every sentence should carry the argument forward.

04
M5 · L5 — Common Mistakes

What beginners do wrong

Five proof
writing mistakes

❌

Asserting without justifying: "Clearly, ℒ ≥ 0." — Never say "clearly" unless you've proved it. It signals you skipped a step.

❌

Missing the QED marker: Without □, readers can't tell where the proof ends. Always close with □ or "This completes the proof."

❌

Overlong proofs: Every sentence should advance the argument. If a sentence just restates what you just said — delete it.

✅

Justify each step explicitly: "(r − ŷ)² ≥ 0 since it is a square of a real number." The italicised phrase is the justification — never skip it.

✅

State what you're proving before you prove it: "We show that ℒ ≥ 0." — one sentence at the start eliminates all ambiguity about what the proof is for.

05
M5 · L5 — Your Exercise

Now you try

Write this proof
in your own words

Proposition. The cosine similarity between any two non-zero vectors p, q ∈ ℝ^d satisfies −1 ≤ cos(p, q) ≤ 1.
[Your proof here. Use the Cauchy-Schwarz inequality: |p^⊤q| ≤ ‖p‖·‖q‖]

Hint: cos(p,q) = p^⊤q / (‖p‖·‖q‖). What does Cauchy-Schwarz tell you about the numerator relative to the denominator?

Structure: Let → By Cauchy-Schwarz → Divide both sides → Conclude → □

Why this matters for RS:

  • Cosine similarity is used in every item-based CF method
  • Showing it's bounded in [-1, 1] justifies it as a similarity measure
  • Cauchy-Schwarz is the most used inequality in ML proofs

Bring your attempt to the next session. Even a rough attempt — partially completed — is better than nothing. I'll give you step-by-step feedback. 🎯

06
M5 Complete — Mathematical Reasoning

Module 5 complete

L1–L2 · Vocabulary

Definitions + Statement types

Term + Domain + Condition. Theorem = major result. Lemma = helper. Corollary = consequence.

L3–L4 · Strategies

Proof structures + Techniques

Direct, contradiction, induction. Bounding, convexity, Lipschitz — the recurring tools in RS proofs.

L5 · Practice

Writing proofs

Statement → Proof. → [steps] → Therefore → □. Justify every step. Never say "clearly." Keep it short.

Next: M6 · Writing Research Papers — framing contributions, introductions, related work

07
← → arrow keys to navigate
1 / 7