Proofs & Proof Techniques

Before we can prove anything, we need to know what kind of thing we are proving.

A proposition is a statement that is either true or false — not both, not neither. "Every even integer greater than 2 is the sum of two primes" is a proposition (Goldbach's conjecture — still unproved!). "This sentence is false" is famously not a proposition (it is a paradox).

A theorem is a proposition that has been proved. A lemma is a helper theorem proved on the way to a larger result. A corollary is a theorem that follows almost immediately from a theorem just proved. These distinctions are social, not logical — they communicate importance and proof structure.

A proof argument uses axioms (statements assumed without proof, like Peano arithmetic or set-theoretic axioms) and previously proved results to derive new truths via inference rules. The most important inference rule in CS is modus ponens: if we know $P$ and we know $P \Rightarrow Q$, then we may conclude $Q$.

A universally quantified statement — "for all integers $n$, ..." — must hold for every element in the domain. A single counterexample demolishes it. An existentially quantified statement — "there exists an integer $n$ such that..." — requires you to produce or guarantee the existence of one witness.

Understanding quantifier scope is half the battle in reading and writing proofs. The statements "for all $x$, there exists $y$ such that $x < y$" and "there exists $y$ such that for all $x$, $x < y$" look similar but are completely different (the first is true for integers; the second is false — no single integer exceeds every other).

# Propositions vs non-propositions

# These are propositions (have definite truth values):
p1 = "17 is prime"                    # True
p2 = "All primes are odd"             # False (2 is even)
p3 = "sqrt(2) is irrational"         # True

# This is NOT a proposition (truth value is undefined without context):
not_a_prop = "x > 5"                 # Depends on x — it's a predicate

# Modus ponens in Python pseudocode:
# If we know: n is even  AND  (n is even => n*n is even)
# Then we can conclude: n*n is even
def even(n): return n % 2 == 0
def modus_ponens_example(n):
    premise1 = even(n)
    premise2 = True  # We have proved: even(n) => even(n*n)
    if premise1 and premise2:
        assert even(n * n)  # Logically guaranteed

This is the most underrated topic in the module, and the place where students lose the most points.

An argument is rigorous when every logical step follows from previously established facts by a valid inference rule, with no hidden gaps, no unexplained jumps, and no unstated assumptions. The standard in mathematics is that any competent reader should be able to verify every step without filling in missing logic themselves.

Four hallmarks of a rigorous proof:

1. State what you are proving. Begin with a crisp restatement of the claim. Do not assume the reader remembers the exact formulation.
2. State your proof strategy. "We proceed by direct proof" or "We assume for contradiction" orients the reader and commits you to a method.
3. Close every gap. Each line should follow from previous lines plus established theorems. When you write "clearly" or "obviously", ask: is it actually obvious, or am I hiding work?
4. Conclude precisely. End with the exact statement you set out to prove, connected back to your argument.

Common informal sins:

• Circular reasoning: assuming the conclusion in the proof ("$n$ is even because $n$ is even").
• Proof by example: showing the statement holds for $n=1,2,3$ and declaring it proved. Examples test propositions; they do not prove universal ones.
• Proof by assertion: writing "it is easy to see that X", when X is non-trivial and the argument is missing.
• Quantifier errors: treating "for all $x$, $P(x)$" as if it said "for some $x$, $P(x)$".

Proof by example is the most common undergraduate error. Verifying the Pythagorean theorem for right triangles with legs 3 and 4 does not prove it for all right triangles.

# Example of a GAP in a proof disguised as code:

# FLAWED argument that all positive integers are equal:
# (Horse paradox style)
def all_equal_BROKEN(n):
    """WRONG: Claims to prove every set of n integers are equal."""
    # Base case: trivially, {a} has all elements equal (n=1).
    # Inductive step: assume true for n, prove for n+1.
    # Take {a1,...,an+1}. By hypothesis {a1,...,an} are equal.
    # By hypothesis {a2,...,an+1} are equal.
    # Therefore a1 = a2 = ... = an+1.   <-- GAP: the two sets
    # must OVERLAP for the argument to work; they don't when n=1!
    pass

# The gap: when n=1, {a1} and {a2} share no element,
# so you cannot chain the equalities. Rigorous proofs
# require checking that the inductive hypothesis actually applies.

The simplest and most natural proof technique: assume the hypotheses and derive the conclusion through a chain of valid inferences.

Direct proof works best when the path from hypothesis to conclusion is constructive — you can explicitly build the thing or compute the value the conclusion claims exists.

Template:

Suppose $P$. [algebraic / logical steps]. Therefore $Q$.

Example 1: The sum of two even integers is even.

Proof. Let $a$ and $b$ be even integers. By definition of even, $a = 2k$ and $b = 2m$ for some integers $k$ and $m$. Then $a + b = 2k + 2m = 2(k+m)$. Since $k+m$ is an integer, $a+b$ is divisible by 2, hence even. $\square$

Notice: every step is justified. We used the definition of even, basic algebra, and the closure of integers under addition. No leaps.

Example 2: If $n$ is odd, then $n^2$ is odd.

Proof. Let $n$ be odd. By definition, $n = 2k+1$ for some integer $k$. Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$. Since $2k^2+2k$ is an integer, $n^2$ has the form $2m+1$ and is therefore odd. $\square$

The power of definitions: Most direct proofs work by unpacking definitions at the start. If you are stuck, write out what every term in the hypothesis and conclusion means formally, and the proof often falls out.

Example 3: Divisibility is transitive. If $a \mid b$ and $b \mid c$, then $a \mid c$.

Proof. By definition, $b = ka$ and $c = mb$ for integers $k, m$. Substituting, $c = m(ka) = (mk)a$. Since $mk$ is an integer, $a \mid c$. $\square$

def is_even(n): return n % 2 == 0

# The theorem says: even + even = even
# Here is a direct proof rendered as code + assertion:
def prove_sum_of_evens_is_even(a, b):
    """Direct proof: a=2k, b=2m => a+b=2(k+m)."""
    assert is_even(a) and is_even(b), "Hypotheses must hold"
    k = a // 2
    m = b // 2
    total = a + b
    witness = k + m          # Explicit integer witness
    assert total == 2 * witness  # Conclusion: total is 2*(integer)
    assert is_even(total)

# Test on several cases — NOT a proof, just a sanity check:
for a, b in [(2,4),(6,100),(0,8),(-4,10)]:
    prove_sum_of_evens_is_even(a, b)

Sometimes the direct path from hypothesis to conclusion is not visible, but if you assume the conclusion is false, you can derive something impossible. That impossibility proves the original conclusion must be true.

Template:

Assume for the sake of contradiction that $\neg Q$. [derive steps]. But this contradicts [some established fact]. Therefore $Q$ must hold. $\square$

The technique is powerful because it gives you an extra hypothesis to work with: the negation of what you are trying to prove.

The classic: $\sqrt{2}$ is irrational.

Proof. Assume for contradiction that $\sqrt{2}$ is rational. Then $\sqrt{2} = p/q$ where $p$ and $q$ are integers with $\gcd(p,q)=1$ (i.e., the fraction is in lowest terms). Squaring: $2 = p^2/q^2$, so $p^2 = 2q^2$. Thus $p^2$ is even, and since the square of an odd number is odd, $p$ must be even. Write $p = 2k$. Then $4k^2 = 2q^2$, giving $q^2 = 2k^2$, so $q^2$ is even, hence $q$ is even. But now both $p$ and $q$ are even, contradicting $\gcd(p,q)=1$. This contradiction shows $\sqrt{2}$ cannot be rational. $\square$

This proof is around 2,500 years old and still beautiful. Every step is forced.

Euclid's infinitely many primes (arguably the greatest proof in the module):

Proof. Assume for contradiction that there are finitely many primes, $p_1, p_2, \ldots, p_k$. Let $N = p_1 p_2 \cdots p_k + 1$. Every integer $\geq 2$ has a prime factor, so $N$ has some prime factor $p$. But $p$ is one of our listed primes $p_i$, so $p \mid p_1 p_2 \cdots p_k$. Since $p \mid N$ and $p \mid p_1 p_2 \cdots p_k$, we get $p \mid 1$, which is impossible for a prime. Contradiction. $\square$

When to use contradiction: When the negation of the conclusion is a strong, usable extra assumption — especially for existence proofs ("there is no...") and for proving that a number is irrational or that sets are infinite.

import math

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(math.isqrt(n)) + 1):
        if n % i == 0: return False
    return True

# Euclid's construction: given a finite list of primes,
# build a number that must have a prime factor NOT in the list.
def euclids_construction(primes):
    """
    Given a claimed 'complete' list of primes,
    constructs N = product + 1 whose prime factors
    are not in the list — the contradiction.
    """
    product = 1
    for p in primes: product *= p
    N = product + 1
    # Find a prime factor of N
    for candidate in range(2, N + 1):
        if N % candidate == 0 and is_prime(candidate):
            assert candidate not in primes, (
                f"{candidate} divides N={N} but wasn't in {primes}!"
            )
            return candidate

# Suppose we naively claim primes = [2, 3, 5]
primes_claim = [2, 3, 5]
new_prime = euclids_construction(primes_claim)
print(f"N = {2*3*5 + 1} = 31, new prime factor: {new_prime}")  # 31

The contrapositive of "$P \Rightarrow Q$" is "$\neg Q \Rightarrow \neg P$". These two statements are logically equivalent — each is true if and only if the other is. So to prove $P \Rightarrow Q$, it is equally valid to prove $\neg Q \Rightarrow \neg P$.

This is subtly different from proof by contradiction. In a contrapositive proof, you are proving a different (but equivalent) implication directly. In contradiction, you are assuming both $P$ and $\neg Q$ and deriving $\bot$ (falsehood).

Template:

We prove the contrapositive. Suppose $\neg Q$. [derive steps]. Therefore $\neg P$. $\square$

Example: If $n^2$ is even, then $n$ is even.

Direct proof is awkward here (you have information about $n^2$ and need to conclude about $n$). The contrapositive is cleaner: "If $n$ is odd, then $n^2$ is odd."

Proof (by contrapositive). We prove: if $n$ is odd, then $n^2$ is odd. Assume $n$ is odd. Then $n = 2k+1$ for some integer $k$. So $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1$, which is odd. $\square$

The original statement follows because we proved its contrapositive.

When to use contrapositive: When you have information about the negation of the conclusion that you can work with productively, and the negation of the hypothesis is what you want to reach. A good heuristic: if the original has the form "if [something complicated] then [property of a number]", try the contrapositive.

Example: If $3 \nmid n^2$, then $3 \nmid n$ (equivalently: contrapositive is "if $3 \mid n$, then $3 \mid n^2$").

Contrapositive: Assume $3 \mid n$. Then $n = 3k$, so $n^2 = 9k^2 = 3(3k^2)$, thus $3 \mid n^2$. $\square$

Do not confuse the contrapositive with the converse. The converse of "$P \Rightarrow Q$" is "$Q \Rightarrow P$", which is a completely different statement (not equivalent to the original). "If $n$ is even then $n^2$ is even" has converse "if $n^2$ is even then $n$ is even" — the converse happens to be true here but that is a separate theorem.

# Contrapositive: (P => Q) is equivalent to (not Q => not P)

# Original: if n^2 is even => n is even
# Contrapositive: if n is odd => n^2 is odd

def prove_via_contrapositive(n):
    """
    Instead of directly proving 'n^2 even => n even',
    we prove the contrapositive 'n odd => n^2 odd'.
    Both are equivalent; pick whichever is easier to work with.
    """
    is_odd = lambda x: x % 2 != 0
    if is_odd(n):
        # Contrapositive hypothesis holds: n is odd
        # Contrapositive conclusion must hold: n^2 is odd
        assert is_odd(n * n), f"Contrapositive fails at n={n}"

# Verify for a range (again: verification, NOT proof)
for n in range(-20, 20):
    prove_via_contrapositive(n)

# The logical equivalence:
from itertools import product as iproduct
print("P=>Q equivalent to notQ=>notP:")
for P, Q in iproduct([True, False], repeat=2):
    forward = (not P) or Q           # P => Q
    contrapos = Q or (not P)  # not(not Q) or not P = Q or not P
    # Wait: not Q => not P = (not(not Q)) or (not P) = Q or not P
    contrapos = (not (not Q)) or (not P)  # simplifies to Q or (not P)
    # Same as forward! Confirmed equivalent.
    assert forward == contrapos

When a universal statement has no single direct argument that works, but the domain naturally splits into several exhaustive cases, and you can prove the statement separately in each case, the proof is valid — because every element of the domain falls into at least one case.

Template:

We split into cases. Case 1: [condition]. [argument]. Case 2: [condition]. [argument]. Since every [object] satisfies Case 1 or Case 2, the proof is complete. $\square$

Key requirement: The cases must be exhaustive (every element falls into at least one case). They do not have to be mutually exclusive (you can overlap), but usually disjoint cases are cleanest.

Example: For every integer $n$, $n(n+1)$ is even.

Proof. We consider two cases.

• Case 1: $n$ is even. Then $n = 2k$, so $n(n+1) = 2k(n+1)$, which is even.
• Case 2: $n$ is odd. Then $n+1 = 2m$ for some integer $m$, so $n(n+1) = n \cdot 2m$, which is even. Since every integer is either even or odd, the proof covers all cases. $\square$

Elegant example: $|ab| = |a||b|$ for real $a, b$.

Cases on the signs of $a$ and $b$: both non-negative, $a < 0$ and $b \geq 0$, $a \geq 0$ and $b < 0$, both negative. Each case is a straightforward computation.

Proof by cases in algorithm analysis: When analyzing quicksort or binary search, you often split on "pivot falls in the left half" vs. "right half". Cases are ubiquitous in algorithms correctness proofs.

A pitfall: Forgetting a case. A proof claiming "$n$ is positive or negative" misses $n = 0$. Always double-check exhaustiveness — especially at boundary conditions.

def prove_n_times_n_plus_1_is_even(n: int) -> bool:
    """
    Proof by cases:
    Case 1: n even  => n*(n+1) = 2k*(n+1)  => even
    Case 2: n odd   => n+1 is even = 2m    => n*(n+1) = n*2m => even
    """
    product = n * (n + 1)
    if n % 2 == 0:
        # Case 1: n is even
        k = n // 2
        assert product == 2 * k * (n + 1)  # Witness for evenness
    else:
        # Case 2: n is odd, so n+1 is even
        m = (n + 1) // 2
        assert product == n * 2 * m        # Witness for evenness
    assert product % 2 == 0
    return True

# Exhaustive check (demonstration):
all(prove_n_times_n_plus_1_is_even(n) for n in range(-50, 50))

# Note the cases are EXHAUSTIVE: every integer is even XOR odd.
# Missing even one case (e.g., n=0) would make the proof INVALID.

Induction is the primary tool for proving statements about all natural numbers (or all elements of a well-ordered set). It deserves its own module (and gets one in the curriculum), but we introduce it here because it is a proof technique at the same level as the others.

The principle: To prove "for all $n \geq n_0$, $P(n)$":

1. Base case: Prove $P(n_0)$ directly.
2. Inductive step: Prove $P(k) \Rightarrow P(k+1)$ for arbitrary $k \geq n_0$. You may assume $P(k)$ (the inductive hypothesis) and must derive $P(k+1)$.

Why does this work? The base case establishes $P(0)$. The inductive step then gives $P(1)$ (from $P(0)$), then $P(2)$ (from $P(1)$), and so on — an infinite chain of implications.

Example: Gauss's sum formula $\sum_{i=1}^n i = n(n+1)/2$.

Base case ($n=1$): $\sum_{i=1}^1 i = 1 = 1 \cdot 2 / 2$. $\checkmark$

Inductive step: Assume $\sum_{i=1}^k i = k(k+1)/2$. Then: $$\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^k i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$$ This is exactly the formula with $n = k+1$. $\square$

Strong induction: The inductive step assumes $P(j)$ for all $j < k$ (not just $j = k-1$). This is logically equivalent to ordinary induction but more powerful for proofs where $P(k+1)$ depends on earlier cases not just $P(k)$. The Fundamental Theorem of Arithmetic (every integer $\geq 2$ is a product of primes) uses strong induction.

The broken induction that proves all horses are the same color (see the "what makes an argument rigorous" concept) is the canonical example of a gap in the inductive step — always verify the step actually works for small $n$, especially $n=1$ to $n=2$.

def gauss_sum(n: int) -> int:
    """Direct formula proved by induction."""
    return n * (n + 1) // 2

# Verify the inductive step programmatically (not a proof!)
def check_inductive_step(k):
    """
    Inductive step: if formula holds for k, verify it holds for k+1
    by checking the recurrence sum(k+1) = sum(k) + (k+1).
    """
    lhs = gauss_sum(k + 1)
    rhs = gauss_sum(k) + (k + 1)   # Using the inductive hypothesis
    return lhs == rhs

assert all(check_inductive_step(k) for k in range(1, 10_000))

# Strong induction example: prime factorization
def has_prime_factorization(n: int) -> bool:
    """Every n >= 2 has a prime factorization (strong induction)."""
    if n < 2: return False
    # Base: n=2 is prime => factorization is {2}
    # Ind. step: if n is prime, done.
    #            if n = a*b with 1<a,b<n, by strong IH both have
    #            factorizations, so n does too.
    return True  # Proof is in the math above, not the code

Many theorems have two parts: something exists, and it is unique. These require distinct proof strategies.

Existence proofs come in two flavors:

1. Constructive: You explicitly exhibit the object. You write down exactly what it is and verify it satisfies the required properties. This is the gold standard when possible.
2. Non-constructive: You prove existence without ever finding the object. Classic tools: contradiction ("if no such object existed, we'd get a contradiction") or probabilistic arguments ("a random choice has positive probability of working, so a good choice exists").

Example (constructive): There exists an integer $n$ such that $n^2 - 3n + 2 = 0$. Proof. Take $n=1$: $1 - 3 + 2 = 0$. $\square$ (Or $n=2$.)

Example (non-constructive): The Intermediate Value Theorem guarantees a root exists for a continuous function that changes sign, without pointing to the root.

Uniqueness proofs have a standard template:

1. Assume there are two objects satisfying the property: call them $x$ and $y$.
2. Show $x = y$.

Example: Multiplicative identity in a field is unique. Suppose $e$ and $e'$ both satisfy $a \cdot e = a$ and $a \cdot e' = a$ for all $a$. Then $e = e \cdot e' = e'$. $\square$

In CS: Existence proofs power complexity theory ("there exists a reduction from A to B") and algorithm design ("there exists an optimal solution satisfying property X"). Uniqueness underpins data structures ("the BST invariant determines a unique sorted order") and type theory ("the principal type of an expression is unique").

# Constructive existence: find x such that x^2 = 2 (mod 7)
def find_sqrt_mod_p(target, p):
    """Constructive existence proof: exhibit the witness."""
    for x in range(p):
        if (x * x) % p == target % p:
            return x  # The witness!
    return None

witness = find_sqrt_mod_p(2, 7)
print(f"Witness: {witness}, check: {witness**2 % 7}")  # 3, check: 2

# Uniqueness template: prove additive identity is unique
def prove_additive_identity_unique():
    """
    Uniqueness proof pattern:
    Assume e and e' are both additive identities.
    Then e = e + e' = e'.
    """
    # Simulated over integers with + as the group operation
    class GroupElement:
        def __init__(self, val): self.val = val
        def op(self, other): return GroupElement(self.val + other.val)
        def __eq__(self, other): return self.val == other.val

    zero_a = GroupElement(0)  # First candidate identity
    zero_b = GroupElement(0)  # Second candidate identity
    x = GroupElement(5)
    # e + x = x  AND  e' + x = x => e = x op e' = x op e (same)
    assert zero_a.op(x) == x == zero_b.op(x)
    assert zero_a == zero_b  # Uniqueness confirmed
    print("Additive identity is unique: e == e'")

The Pigeonhole Principle states: if $n+1$ objects are placed into $n$ containers, then at least one container holds at least 2 objects. This seems trivially obvious, but it is proved rigorously by contradiction — and it unlocks an astonishing range of theorems.

Proof (by contradiction). Suppose not: every container holds at most 1 object. Then the total number of objects is at most $n \cdot 1 = n$. But we placed $n+1$ objects. Contradiction. $\square$

The generalized version: If $mn+1$ objects are placed into $n$ containers, some container holds at least $m+1$ objects.

CS Applications:

• Hash functions: Any hash function mapping more inputs than outputs must have a collision. There is no perfect hash function for a domain larger than the codomain. (Proof: map $|\text{domain}|$ pigeons into $|\text{codomain}|$ holes.)
• Birthdays: In a group of 367 people, at least two share a birthday.
• Repeated state in computation: A finite-state machine on an infinite input must revisit a state (used in the pumping lemma for regular languages).
• Compression: No lossless compression algorithm can compress every file (some files must get longer or stay the same size). If you have $2^n$ possible $n$-bit strings and compress each to fewer than $n$ bits, you'd need to store them in a smaller set — which by pigeonhole must cause collisions.

The power of this principle is that it proves existence without construction. You prove a collision exists without ever finding it. This is the quintessential non-constructive argument.

# Pigeonhole: prove (by construction in finite case) that
# a hash function on a small domain has collisions.

from collections import defaultdict

def demonstrate_pigeonhole_collision(num_items: int, num_buckets: int):
    """
    Pigeonhole principle: if num_items > num_buckets,
    some bucket has >= 2 items.
    """
    assert num_items > num_buckets, "Need more items than buckets!"
    buckets = defaultdict(list)
    for item in range(num_items):
        h = item % num_buckets  # Any hash function — collision must exist
        buckets[h].append(item)
    collisions = {k: v for k, v in buckets.items() if len(v) >= 2}
    assert len(collisions) > 0, "Pigeonhole guarantees this!"
    return collisions

print(demonstrate_pigeonhole_collision(10, 7))
# e.g., {0: [0, 7], 1: [1, 8], 2: [2, 9]}

# The PROOF is not the code above — the code just ILLUSTRATES.
# The proof is: if every bucket had <= 1 item, total <= num_buckets < num_items. Contradiction.

Even students who understand the techniques make systematic errors. Knowing the error patterns is half the defense.

1. Division by zero in disguise. The classic "proof" that $1 = 2$: let $a = b$; then $a^2 = ab$; subtract $b^2$: $a^2 - b^2 = ab - b^2$; factor: $(a-b)(a+b) = b(a-b)$; divide both sides by $(a-b)$: $a+b = b$; since $a=b$: $2b = b$; so $2 = 1$. The error: dividing by $(a-b) = 0$.

2. Treating implication as equivalence. $P \Rightarrow Q$ does not mean $Q \Rightarrow P$. After squaring both sides of an equation, you may introduce extraneous solutions. Proofs that involve non-reversible steps must be checked going both directions if you need an if-and-only-if.

3. Off-by-one in induction. Failing to verify the base case, or writing an inductive step that actually requires $k \geq 2$ when the base case only establishes $k = 0$. Classic: proofs by induction where the step requires two prior values (Fibonacci-style) need two base cases.

4. Assuming the hypothesis is the conclusion. Circular reasoning: "$n$ is prime, so $n$ has no divisors other than 1 and $n$, so $n$ is prime". Each step individually may be valid, but the chain is circular.

5. Mishandling quantifiers. Swapping $\forall$ and $\exists$. Writing "let $x$ be arbitrary" and then using a specific property of $x$ that is not given (you invented a witness when you needed to show universality, or vice versa).

6. Incomplete case analysis. Missing the zero case, the negative case, the boundary case. Computer scientists are especially susceptible — we are used to assuming inputs are "nice".

7. Appealing to intuition on infinite sets. Intuition fails for infinities. The set of even numbers and the set of natural numbers have the same cardinality (both countably infinite) even though the evens seem "half as many". Never trust geometric or physical intuition about infinite domains without a rigorous argument.

The checklist before submitting any proof:

• Did I prove what I claimed, or something slightly different?
• Are my cases exhaustive?
• Did I assume anything I didn't state?
• Did I use any implication in the wrong direction?
• Does the argument still work at the boundary values?

# Demonstration of the classic "1 = 2" fake proof (commented)

def fake_proof_one_equals_two():
    """
    Let a = b = 1.
    a^2 = a*b       (multiply both sides of a=b by a)
    a^2 - b^2 = a*b - b^2  (subtract b^2)
    (a-b)(a+b) = b(a-b)    (factor)
    a+b = b                 <--- DIVISION BY ZERO: a-b = 0 !
    2b = b
    2 = 1
    """
    a = b = 1.0
    lhs = a*a - b*b   # = 0
    rhs = a*b - b*b   # = 0
    # INVALID: (lhs / (a - b)) — a-b is ZERO
    try:
        result = lhs / (a - b)
    except ZeroDivisionError:
        print("Caught the error! Division by (a-b)=0 is undefined.")

fake_proof_one_equals_two()

# Moral: every algebraic step in a proof must be valid.
# Division is only valid when the divisor is NONZERO.
# In a proof, you must either prove it's nonzero, or case-split.