Exercises Notebook

Converted from exercises.ipynb for web reading.

Proof Techniques - Exercises

This notebook contains 10 progressive exercises for 06-Proof-Techniques. Each exercise has a learner workspace followed by a complete reference solution. The goal is fluent foundational math for later linear algebra, calculus, probability, and ML sections.

Code cell 2

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

try:
    import seaborn as sns
    sns.set_theme(style="whitegrid", palette="colorblind")
    HAS_SNS = True
except ImportError:
    plt.style.use("seaborn-v0_8-whitegrid")
    HAS_SNS = False

mpl.rcParams.update({
    "figure.figsize":    (10, 6),
    "figure.dpi":         120,
    "font.size":           13,
    "axes.titlesize":      15,
    "axes.labelsize":      13,
    "xtick.labelsize":     11,
    "ytick.labelsize":     11,
    "legend.fontsize":     11,
    "legend.framealpha":   0.85,
    "lines.linewidth":      2.0,
    "axes.spines.top":     False,
    "axes.spines.right":   False,
    "savefig.bbox":       "tight",
    "savefig.dpi":         150,
})
np.random.seed(42)
print("Plot setup complete.")

Code cell 3

import numpy as np
import numpy.linalg as la
from decimal import Decimal, getcontext
from itertools import product

np.set_printoptions(precision=8, suppress=True)
np.random.seed(42)

def header(title):
    print("\n" + "=" * len(title))
    print(title)
    print("=" * len(title))

def check_true(name, cond):
    ok=bool(cond)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    return ok

def check_close(name, got, expected, tol=1e-8):
    ok=np.allclose(got, expected, atol=tol, rtol=tol)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    if not ok:
        print('  got     =', got)
        print('  expected=', expected)
    return ok

def powerset(s):
    items=list(s)
    return [set(items[i] for i in range(len(items)) if mask & (1 << i)) for mask in range(1 << len(items))]

print("Chapter 01 helper setup complete.")

Exercise 1: Direct Proof by Exhaustion

Verify even-plus-even is even over a finite sample.

Code cell 5

# Your Solution
# Exercise 1 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 1.")

Code cell 6

# Solution
# Exercise 1 - Direct Proof by Exhaustion
header("Exercise 1: direct proof sample")
vals=[]
for a in range(-4,5,2):
    for b in range(-4,5,2): vals.append((a+b)%2==0)
check_true("all sampled sums even", all(vals))

Exercise 2: Contrapositive

For integers in a sample, verify if $n^2$ is odd then $n$ is odd.

Code cell 8

# Your Solution
# Exercise 2 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 2.")

Code cell 9

# Solution
# Exercise 2 - Contrapositive
header("Exercise 2: contrapositive")
for n in range(-10,11):
    if n*n%2==1: check_true(f"n={n} odd", n%2==1)

Exercise 3: Contradiction Pattern

Show no integer in a sample satisfies $n^2=2$.

Code cell 11

# Your Solution
# Exercise 3 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 3.")

Code cell 12

# Solution
# Exercise 3 - Contradiction Pattern
header("Exercise 3: contradiction sample")
solutions=[n for n in range(-10,11) if n*n==2]
print("solutions", solutions)
check_true("no integer square equals 2", len(solutions)==0)

Exercise 4: Induction Sum Formula

Check base and inductive step numerically for $1+...+n$.

Code cell 14

# Your Solution
# Exercise 4 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 4.")

Code cell 15

# Solution
# Exercise 4 - Induction Sum Formula
header("Exercise 4: induction sum")
S=lambda n:n*(n+1)//2
check_true("base", S(1)==1)
for n in range(1,20): check_true(f"step {n}", S(n)+(n+1)==S(n+1))

Exercise 5: Geometric Induction

Verify a recursive geometric sum identity.

Code cell 17

# Your Solution
# Exercise 5 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 5.")

Code cell 18

# Solution
# Exercise 5 - Geometric Induction
header("Exercise 5: geometric induction")
r=0.5
for n in range(1,10):
    lhs=sum(r**i for i in range(n+1)); rhs=sum(r**i for i in range(n))+r**n
    check_close(f"step {n}", lhs, rhs)

Exercise 6: Counterexample

Disprove all matrices commute with a small pair.

Code cell 20

# Your Solution
# Exercise 6 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 6.")

Code cell 21

# Solution
# Exercise 6 - Counterexample
header("Exercise 6: counterexample")
A=np.array([[0.,1.],[0.,0.]]); B=np.array([[0.,0.],[1.,0.]])
print("AB\n",A@B,"BA\n",B@A)
check_true("not commute", not np.allclose(A@B,B@A))

Exercise 7: Invariant

Check that gradient descent on a diagonal quadratic preserves zero coordinates.

Code cell 23

# Your Solution
# Exercise 7 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 7.")

Code cell 24

# Solution
# Exercise 7 - Invariant
header("Exercise 7: invariant")
H=np.diag([1.,2.,3.]); x=np.array([1.,0.,2.]); eta=0.1
for _ in range(20): x=x-eta*(H@x)
print("x", x)
check_close("middle coordinate remains zero", x[1], 0.0)

Exercise 8: Proof by Cases

Verify absolute value identity $|x|=x$ if $x>=0$ else $-x$.

Code cell 26

# Your Solution
# Exercise 8 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 8.")

Code cell 27

# Solution
# Exercise 8 - Proof by Cases
header("Exercise 8: cases")
xs=np.array([-3.,0.,2.])
case=np.where(xs>=0,xs,-xs)
check_close("abs by cases", case, np.abs(xs))

Exercise 9: Assumption Check

Show a theorem can fail when a hypothesis is removed: non-PD matrix has no Cholesky.

Code cell 29

# Your Solution
# Exercise 9 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 9.")

Code cell 30

# Solution
# Exercise 9 - Assumption Check
header("Exercise 9: hypothesis matters")
A=np.array([[1.,2.],[2.,1.]])
try:
    la.cholesky(A)
    ok=False
except la.LinAlgError:
    ok=True
check_true("Cholesky needs PD", ok)

Exercise 10: Numerical Proof Sanity

Use random tests as evidence, then state they are not proof.

Code cell 32

# Your Solution
# Exercise 10 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 10.")

Code cell 33

# Solution
# Exercise 10 - Numerical Proof Sanity
header("Exercise 10: tests are not proof")
rng=np.random.default_rng(0)
passed=True
for _ in range(100):
    A=rng.normal(size=(3,3)); x=rng.normal(size=3); y=rng.normal(size=3)
    passed &= np.allclose(A@(x+y), A@x + A@y)
check_true("linearity tests pass", passed)
print("Takeaway: tests find bugs; proofs explain all cases.")