How to read and write a proof

Before this lesson: lesson 02 (sets, $\Sigma$, $\forall$, $\exists$, $\Rightarrow$). Some examples use lesson 05 (softmax) and lesson 08 (the mean). Time: about 60 minutes, plus the notebook. Next: the numbered proofs in Linear Algebra lesson 01 and in every other track.

---

Why this matters #

Every later track states theorems and proves them, and ML papers use the same language. A theorem tells you exactly when a method works. For example: "if $f$ is convex and its gradient is $L$-Lipschitz, then gradient descent with step size $\eta \le 1/L$ satisfies $f(x_k) - f(x^\star) \le \frac{\|x_0 - x^\star\|^2}{2\eta k}$". To use it, you must check the assumptions. The loss of a neural network is not convex, so this theorem does not apply to it directly; that is a research question, not a detail. The Optimization track proves this result.

Proofs also help you write correct code. A loop is correct by an induction argument (a loop invariant). Backpropagation is correct because the chain rule holds at every layer, one layer after another. And a single counterexample can stop a wrong idea early, such as "a single linear unit can learn XOR" (section 4b).

1. Predict first #

2. The picture #

2.1 An implication is a statement about sets #

"For every $n$: if $P(n)$, then $Q(n)$" is written $P \Rightarrow Q$. Think of two sets: the numbers where $P$ holds and the numbers where $Q$ holds. The claim says that the $P$-set lies inside the $Q$-set. A counterexample is a number in the $P$-set but outside the $Q$-set.

Interactive figure: loading…

2.2 Induction is a row of dominoes #

Let $P(n)$ be a statement for each $n = 1, 2, 3, \dots$, for example "$1 + 2 + \dots + n = n(n+1)/2$". Picture one domino per statement. The base case pushes the first domino: we prove $P(1)$. The induction step puts the dominoes close enough together: we prove that if domino $k$ falls, domino $k + 1$ falls, for every $k$. Then all dominoes fall. Both parts are needed.

Interactive figure: loading…

2.3 A picture proof of a sum #

Why is $1 + 2 + \dots + n = \frac{n(n+1)}{2}$? Draw the sum as a staircase of squares: column $i$ has $i$ squares. Turn a copy of the staircase upside down and put it on top. The two staircases fill a rectangle with $n$ columns and $n + 1$ rows. So two staircases have $n(n + 1)$ squares, and one has $n(n+1)/2$.

Interactive figure: loading…

3. Definitions and main results #

3.1 The words of mathematics #

• A definition gives a precise meaning to a word. "An integer $n$ is even if $n = 2k$ for some integer $k$." Proofs about even numbers start from this sentence.
• A theorem is an important true claim with a proof. A lemma is a smaller result used to prove a theorem. A corollary follows quickly from a theorem. A conjecture is a claim that nobody has proved yet.
• A proof ends with $\blacksquare$ (or "QED"). In this site, long proofs are numbered step by step.

Most theorems have the form "assumptions $\Rightarrow$ conclusion". In "if $f$ is convex and differentiable, then every point with $\nabla f(x) = 0$ is a global minimum", the assumptions are "convex" and "differentiable", and the conclusion is "global minimum".

3.2 Implications, converse, contrapositive #

A statement is true or false. For statements $P$ and $Q$:

$P$	$Q$	$P \Rightarrow Q$	converse $Q \Rightarrow P$	contrapositive $\neg Q \Rightarrow \neg P$
true	true	true	true	true
true	false	false	true	false
false	true	true	false	true
false	false	true	true	true

Here $\neg P$ means "not $P$". Read the table row by row.

• $P \Rightarrow Q$ is false only in one case: $P$ true and $Q$ false. When $P$ is false, the implication makes no promise, so it counts as true.
• The contrapositive $\neg Q \Rightarrow \neg P$ has the same column as $P \Rightarrow Q$: they are equivalent. A proof of one is a proof of the other.
• The converse $Q \Rightarrow P$ has a different column. It is a different claim.
• If and only if ("iff", $P \Leftrightarrow Q$) means both $P \Rightarrow Q$ and $Q \Rightarrow P$. A proof of an iff has two parts, one for each direction.

3.3 Quantifiers and how to negate them #

$\forall x$ means "for every $x$"; $\exists x$ means "there exists (at least one) $x$". To negate a statement, swap the quantifiers and negate the inside:

So "not every number is even" means "some number is odd". This is why one counterexample disproves a "for all" claim.

The order matters. On the real numbers:

• $\forall x\ \exists y : y > x$ ("for every number there is a larger one") is true: take $y = x + 1$.
• $\exists y\ \forall x : y > x$ ("there is a number larger than every number") is false: no $y$ is larger than $y + 1$.

In the first statement, $y$ may depend on $x$. In the second, one $y$ must work for all $x$. Negating the first statement step by step: $\neg(\forall x\ \exists y : y > x) \equiv \exists x\ \neg(\exists y : y > x) \equiv \exists x\ \forall y : y \le x$.

3.4 How to read a proof #

1. Restate the claim in your own words. Name the assumptions and the conclusion.
2. Try a small case with numbers. It shows what the claim says and makes the steps concrete.
3. For each line, ask: which fact gives this? A definition, an assumption, an earlier line, or a known result. If you cannot answer, slow down; that line is where the idea is.
4. Find where each assumption is used. If an assumption is never used, either the theorem is more general than stated, or you missed a step. If you drop an assumption, look for a counterexample.

3.5 Direct proof #

Start from the assumptions and go step by step to the conclusion.

Claim. The sum of two even integers is even. Proof. Let $m$ and $n$ be even. By the definition, $m = 2a$ and $n = 2b$ for some integers $a, b$. Then $m + n = 2a + 2b = 2(a + b)$, and $a + b$ is an integer. So $m + n$ is even. $\blacksquare$

Claim. For all real $x, y$: $x^2 + y^2 \ge 2xy$. Proof. A square is never negative, so $(x - y)^2 \ge 0$. Expand: $x^2 - 2xy + y^2 \ge 0$. Add $2xy$ to both sides: $x^2 + y^2 \ge 2xy$. $\blacksquare$ (Equality holds exactly when $x = y$. Finding the right starting fact, here $(x-y)^2 \ge 0$, is the creative part.)

Claim (softmax is shift invariant, lesson 05). For every vector $z \in \R^n$ and every number $c$: $\operatorname{softmax}(z + c) = \operatorname{softmax}(z)$, where $z + c$ adds $c$ to every entry. Proof. For each $k$,

We used $e^{a + b} = e^a e^b$, pulled the common factor $e^c$ out of the sum, and cancelled it ($e^c > 0$, so it is not 0). $\blacksquare$

3.6 Proof by contrapositive #

To prove $P \Rightarrow Q$, prove $\neg Q \Rightarrow \neg P$ instead (section 3.2). Use it when "not $Q$" gives you something concrete to work with.

Claim. For every integer $n$: if $n^2$ is even, then $n$ is even. Proof. We prove the contrapositive: if $n$ is odd, then $n^2$ is odd. Let $n$ be odd, so $n = 2k + 1$ for an integer $k$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. $\blacksquare$

A direct proof is hard here: "$n^2 = 2m$" says little about $n$ itself. The contrapositive starts from $n$.

3.7 Proof by contradiction #

To prove a statement $S$, assume $\neg S$ and derive something impossible: a statement and its negation at the same time. Then $\neg S$ cannot hold, so $S$ is true.

Theorem. $\sqrt 2$ is irrational: there are no integers $p, q$ with $q \ne 0$ and $\sqrt 2 = p/q$.

Proof.

1. Assume the opposite: $\sqrt 2 = p/q$ for some integers $p, q$ with $q \ne 0$.
2. Cancel common factors, so that the fraction is in lowest terms: $p$ and $q$ have no common factor larger than 1. (Every fraction can be reduced like this.)
3. Square: $2 = p^2/q^2$, so $p^2 = 2q^2$. Hence $p^2$ is even.
4. By the claim of section 3.6, $p$ is even: $p = 2r$ for an integer $r$.
5. Put this into step 3: $4r^2 = 2q^2$, so $q^2 = 2r^2$. Hence $q^2$ is even, and (section 3.6 again) $q$ is even.
6. Now $p$ and $q$ are both even, so 2 is a common factor. This contradicts step 2.
7. So the assumption in step 1 is false, and $\sqrt 2$ is irrational. $\blacksquare$

There are infinitely many prime numbers (Euclid)

1. Assume the opposite: there are only finitely many primes, $p_1, p_2, \dots, p_k$.
2. Let $N = p_1 p_2 \cdots p_k + 1$. Then $N > 1$, so $N$ has at least one prime factor $q$.
3. $q$ is one of the $p_i$, because the list contains all primes. But dividing $N$ by any $p_i$ leaves the remainder 1, so $p_i$ does not divide $N$. Contradiction.
4. So there are infinitely many primes. $\blacksquare$

Careful: the proof does not say that $N$ itself is prime. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$.

3.8 Proof by induction #

Principle of induction. Let $P(n)$ be a statement for each integer $n \ge n_0$. If

1. base case: $P(n_0)$ is true, and
2. induction step: for every $k \ge n_0$, $P(k) \Rightarrow P(k + 1)$,

then $P(n)$ is true for every $n \ge n_0$.

In the step, $P(k)$ is called the induction hypothesis. Assuming it is not circular: the step does not claim that $P(k)$ is true. It proves the implication "if $P(k)$, then $P(k + 1)$". Truth enters only through the base case, and then flows along the implications: $P(n_0)$, then $P(n_0 + 1)$, and so on.

Theorem. For every $n \ge 1$: $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.

Proof.

1. Base case, $n = 1$: the left side is 1 and the right side is $\frac{1 \cdot 2}{2} = 1$.
2. Step. Let $k \ge 1$ and assume $1 + \dots + k = \frac{k(k+1)}{2}$ (induction hypothesis).
3. Then $1 + \dots + k + (k + 1) = \frac{k(k+1)}{2} + (k + 1)$ by the hypothesis.
4. $= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$, which is the formula for $n = k + 1$. $\blacksquare$

Step 3 is the yellow column of the staircase figure.

The base case matters. Claim: $2^n > n^2$ for every $n \ge 5$.

$n$	1	2	3	4	5	6	7
$2^n$	2	4	8	16	32	64	128
$n^2$	1	4	9	16	25	36	49
$2^n > n^2$?	yes	no	no	no	yes	yes	yes

The step works for every $k \ge 3$ (section 4c), but $P(3)$ and $P(4)$ are false, so the chain can only start at $n_0 = 5$. A correct step without a true base case proves nothing.

A broken induction: "all horses have the same colour". Let $P(n)$ be "in every group of $n$ horses, all horses have the same colour". $P(1)$ is true. "Step": take a group of $k + 1$ horses. Remove the first horse: the remaining $k$ have one colour, by $P(k)$. Remove the last horse instead: those $k$ also have one colour. The two groups overlap, so all $k + 1$ horses have the same colour.

Where is the error? For $k = 1$ (going from 1 to 2 horses), the two groups are {horse 2} and {horse 1}. They do not overlap, so the colours need not match. The step fails at $k = 1$, so nothing beyond $P(1)$ follows. The step must work for every $k \ge n_0$.

3.9 Counterexamples #

One counterexample proves that a "for all" claim is false (section 3.3). Examples:

• "$n^2 + n + 41$ is prime for every integer $n \ge 0$." It is prime for $n = 0, 1, \dots, 39$, but $40^2 + 40 + 41 = 1681 = 41^2$.
• "$\log(a + b) = \log a + \log b$." False: $a = b = 1$ gives $\log 2 \approx 0.693$ on the left and $0$ on the right. The true rule is $\log(ab) = \log a + \log b$.
• "$AB = BA$ for square matrices." False: $A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$, $B = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ give $AB = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$ and $BA = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$.

Many examples never prove a "for all" claim. A famous case is Pólya's conjecture from number theory: it holds for every $n$ from 2 up to 906 150 256, and fails at $n = 906\,150\,257$. Checking is the best way to find counterexamples, and a good way to test a claim before you try to prove it. It is not a proof.

Interactive figure: loading…

Answers to section 1. (1) No. That is the converse, and $n = 2$ is a counterexample: it is even but not divisible by 4. (2) No. A check of finitely many cases cannot cover all integers; the next case may fail, as in Pólya's conjecture. You need a proof. (3) No. The step proves only the implication "if $P(k)$, then $P(k + 1)$". The base case supplies the first true statement (section 3.8).

4. Worked example #

(a) The mean minimizes the squared error (used in lesson 08 and in every regression model).

Claim. Let $x_1, \dots, x_n$ be real numbers with mean $\bar x$, and let $f(c) = \sum_{i=1}^n (x_i - c)^2$. Then $f(c) \ge f(\bar x)$ for every real $c$, with equality only for $c = \bar x$.

Small case first. For the data $1, 2, 6$: $\bar x = 3$, $f(3) = 4 + 1 + 9 = 14$, $f(2) = 1 + 0 + 16 = 17$, $f(4) = 9 + 4 + 4 = 17$. The value at the mean is the smallest of the three.

Proof.

1. Write $x_i - c = (x_i - \bar x) + (\bar x - c)$. (Add and subtract $\bar x$; this is the idea of the proof.)
2. Square: $(x_i - c)^2 = (x_i - \bar x)^2 + 2(x_i - \bar x)(\bar x - c) + (\bar x - c)^2$.
3. Sum over $i$. The middle term is $2(\bar x - c)\sum_i (x_i - \bar x)$, and $\sum_i (x_i - \bar x) = 0$ (lesson 08, section 3.3). The last term does not depend on $i$, so it gives $n(\bar x - c)^2$.
4. So $f(c) = \sum_i (x_i - \bar x)^2 + n(\bar x - c)^2 = f(\bar x) + n(\bar x - c)^2$.
5. $n(\bar x - c)^2 \ge 0$, with equality only when $c = \bar x$. So $f(c) \ge f(\bar x)$, with equality only for $c = \bar x$. $\blacksquare$

Check with the small case: $f(2) = 14 + 3 \cdot 1^2 = 17$ ✓. Where was each fact used? Step 3 uses the definition of $\bar x$; step 5 uses "a square is never negative" and $n > 0$.

(b) A single linear unit cannot compute XOR (proof by contradiction). A linear threshold unit outputs 1 if $w_1 x_1 + w_2 x_2 + b > 0$ and 0 otherwise. XOR outputs 1 exactly when one input is 1 and the other is 0.

1. Assume the opposite: some $w_1, w_2, b$ give XOR on all four inputs.
2. Input $(0, 0)$ must give 0, so $b \le 0$.
3. Inputs $(1, 0)$ and $(0, 1)$ must give 1, so $w_1 + b > 0$ and $w_2 + b > 0$.
4. Input $(1, 1)$ must give 0, so $w_1 + w_2 + b \le 0$.
5. Add the two inequalities of step 3: $w_1 + w_2 + 2b > 0$, so $w_1 + w_2 + b > -b$.
6. By step 2, $-b \ge 0$. So $w_1 + w_2 + b > 0$. This contradicts step 4.
7. So no such $w_1, w_2, b$ exist. $\blacksquare$

This is why networks need a hidden layer (Minsky and Papert, 1969). A two-layer network computes XOR easily.

(c) The induction step for $2^n > n^2$, written in full.

Claim. For every $n \ge 5$: $2^n > n^2$.

1. Base case, $n = 5$: $2^5 = 32 > 25 = 5^2$.
2. Step. Let $k \ge 5$ and assume $2^k > k^2$.
3. Then $2^{k+1} = 2 \cdot 2^k > 2k^2$ by the hypothesis.
4. We want $2k^2 \ge (k + 1)^2$. Expand: $(k+1)^2 = k^2 + 2k + 1$, so we need $k^2 \ge 2k + 1$, that is, $k^2 - 2k - 1 \ge 0$, that is, $(k - 1)^2 \ge 2$.
5. For $k \ge 5$, $(k - 1)^2 \ge 16 \ge 2$. (Step 4 even holds for every $k \ge 3$.)
6. So $2^{k+1} > 2k^2 \ge (k + 1)^2$: this is $P(k + 1)$. $\blacksquare$

5. In code #

Code cannot prove a "for all" claim, but it finds counterexamples quickly and checks claims on many cases before you try to prove them. The notebook for this lesson has these cells and the exercises.

import itertools
import numpy as np

def is_prime(m):
    return m >= 2 and all(m % d for d in range(2, int(m**0.5) + 1))

# a counterexample: the first n with n^2 + n + 41 not prime
n = next(n for n in itertools.count() if not is_prime(n * n + n + 41))
print(n, n * n + n + 41, 41 * 41)          # 40 1681 1681

# 2^n > n^2 holds for n = 1 and n >= 5 (checked here up to 60; the proof covers all n)
print([n for n in range(1, 61) if not 2**n > n**2])   # [2, 3, 4]

# Gauss's formula, checked for n = 1..1000 (a check, not a proof)
print(all(sum(range(1, n + 1)) == n * (n + 1) // 2 for n in range(1, 1001)))   # True

# truth table: P => Q is "not P or Q"; the contrapositive has the same column
imp = lambda p, q: (not p) or q
for P, Q in itertools.product([True, False], repeat=2):
    print(P, Q, imp(P, Q), imp(Q, P), imp(not Q, not P))
# True True True True True
# True False False True False
# False True True False True
# False False True True True

# the mean minimizes the sum of squared distances (on a grid of candidates c)
x = np.array([1., 2., 6.])
c = np.linspace(0, 6, 601)
f = ((x[:, None] - c[None, :])**2).sum(axis=0)
print(c[f.argmin()], f.min())               # 3.0 14.0

6. Where it shows up #

• Reading theorems in the other tracks. Every lesson in Linear Algebra states and proves results with numbered steps. For example, the spectral theorem is proved by induction on the size of the matrix: a symmetric $n \times n$ problem is reduced to a symmetric $(n-1) \times (n-1)$ one.
• Convergence results. Optimization theorems ("gradient descent converges if …") have precise assumptions: convexity, smoothness, a step size bound. Checking them is the first thing to do when you apply such a result.
• Algorithms. A loop invariant is an induction: it holds before the first iteration (base case) and each iteration keeps it (step). Dynamic programming and the Bellman equation in reinforcement learning are argued the same way, one step at a time.
• Backpropagation. The gradient at layer $\ell$ is correct if the gradient at layer $\ell + 1$ is correct and the chain rule holds for that layer: an induction over the layers, from the output back to the input.
• Impossibility results. The XOR proof of section 4b, the no-free-lunch theorems and lower bounds on sample complexity are proofs that something cannot be done. They tell you which model class or how much data you need.
• Counterexamples in practice. A failing unit test is a counterexample. Adversarial examples are counterexamples to "the classifier is correct near every training image".

7. Common mistakes #

• Proving the converse. You want $P \Rightarrow Q$ but you show $Q \Rightarrow P$. Write the assumptions and the conclusion on top of your proof, and check that you start from the assumptions.
• "I checked many cases, so it is true." Examples only show that no counterexample was found yet.
• Forgetting the base case, or checking the wrong one. For $2^n > n^2$, the step works from $k = 3$, but the claim is false for $n = 3$ and $4$.
• A step that does not work for every $k$. The horses argument fails at $k = 1$. Check the step for the smallest $k$ too.
• Assuming what you want to prove. In a proof by contradiction you assume the negation of the claim, not the claim. In an induction step you may use $P(k)$, not $P(k + 1)$.
• Negating a statement wrongly. The negation of "every $x$ has property $P$" is "some $x$ does not have $P$", not "no $x$ has $P$".
• Hidden division by zero. A chain of equations that divides by $a - b$ is wrong when $a = b$.
• Thinking Euclid's $N = p_1 \cdots p_k + 1$ is prime. It only has a prime factor outside the list; $30031 = 59 \cdot 509$.

8. Check yourself #

1. Write the converse and the contrapositive of "if a function is differentiable at $x$, then it is continuous at $x$". Which of the two is true?
   Answer

   Converse: "if it is continuous at $x$, then it is differentiable at $x$". It is false: $f(x) = |x|$ is continuous at 0 but has a corner there. Contrapositive: "if it is not continuous at $x$, then it is not differentiable at $x$". It is true, because it is equivalent to the original statement, which is a theorem of calculus.
2. Negate "every student passed at least one exam". Write it with quantifiers first.
   Answer

   $\forall s\ \exists e$: $s$ passed $e$. The negation is $\exists s\ \forall e$: $s$ did not pass $e$. In words: "some student failed every exam".
3. Prove that the product of two odd integers is odd.
   Answer

   Let $m = 2a + 1$ and $n = 2b + 1$. Then $mn = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1$, and $2ab + a + b$ is an integer. So $mn$ is odd. $\blacksquare$
4. Prove by induction: $1 + 3 + 5 + \dots + (2n - 1) = n^2$ for every $n \ge 1$.
   Answer

   Base case: $n = 1$ gives $1 = 1^2$. Step: assume $1 + 3 + \dots + (2k - 1) = k^2$. Add the next odd number, $2(k + 1) - 1 = 2k + 1$: the sum becomes $k^2 + 2k + 1 = (k + 1)^2$. $\blacksquare$
5. Find the error: "Let $a = b$. Then $a^2 = ab$, so $a^2 - b^2 = ab - b^2$, so $(a - b)(a + b) = b(a - b)$, so $a + b = b$, so $2b = b$, so $2 = 1$."
   Answer

   The step from $(a - b)(a + b) = b(a - b)$ to $a + b = b$ divides by $a - b$, which is 0 because $a = b$. Division by zero is not allowed, so the chain breaks there.
6. Is "$n^2 - n + 41$ is prime for every integer $n \ge 1$" true?
   Answer

   No. For $n = 41$: $41^2 - 41 + 41 = 41^2 = 1681$, which is not prime. (It is prime for $n = 1, \dots, 40$, which shows again that many checked cases prove nothing.)

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is the contrapositive of $P \Rightarrow Q$, and is it equivalent to it?

   Show answer

2. What is the converse of $P \Rightarrow Q$, and is it equivalent to it?

   Show answer

3. When is the implication $P \Rightarrow Q$ false?

   Show answer

4. Negate $\forall x : P(x)$.

   Show answer

5. What are the two parts of a proof by induction?

   Show answer

6. Why is assuming $P(k)$ in an induction step not circular?

   Show answer

7. What is the structure of a proof by contradiction?

   Show answer

8. What does one counterexample do to a "for all" claim, and what do many examples do?

   Show answer

9. In the proof that $\sqrt 2$ is irrational, what is contradicted?

   Show answer

10. Compute $1 + 2 + \dots + 100$.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Prove that $\sqrt 2$ is irrational." — Contradiction with a fraction in lowest terms (section 3.7). Know which step uses "$n^2$ even ⇒ $n$ even" and how that is proved (contrapositive).
• "Prove $1 + 2 + \dots + n = n(n+1)/2$." — Induction, or the picture with two staircases, or Gauss's trick: write the sum forwards and backwards and add.
• "Why can a single perceptron not learn XOR?" — The four inequalities of section 4b contradict each other: XOR is not linearly separable.
• "Show that the mean minimizes the squared error, and the median the absolute error." — Section 4a for the mean. For the median: moving $c$ to the right by a small step changes $\sum_i |x_i - c|$ by (points left of $c$ − points right of $c$) × step, so the minimum is where both counts are equal.
• "Your colleague tested the claim on 10 000 random inputs. Is it correct?" — Not proved. Ask for the argument, look for edge cases (0, negative numbers, ties, empty input), and try to build a counterexample.

10. Practice #

The notebook for this lesson runs in Colab or in your browser. Code checks claims; it does not prove them. The notebook says this again in each exercise. Five exercises, each with a check cell and a folded solution:

1. Find the first $n$ for which $n^2 + n + 41$ is not prime.
2. Check $\sum_{i=1}^n i = n(n+1)/2$ and $\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6$ for every $n \le 1000$.
3. Build the truth tables of $P \Rightarrow Q$, its converse and its contrapositive with itertools.product.
4. Find the smallest $n_0$ such that $2^n > n^2$ for every $n$ from $n_0$ to 200.
5. Check on a grid that the mean minimizes $\sum_i (x_i - c)^2$, then read the proof in the solution.

11. Watch and read #

Lec 1 | MIT 6.042J Mathematics for Computer Science, Fall 2010MIT OpenCourseWare · Tom Leighton · 44 min

What a proof is, and why checking many cases is not enough.

Lec 2 | MIT 6.042J Mathematics for Computer Science, Fall 2010MIT OpenCourseWare · Tom Leighton · 79 min

Proof by induction, with several examples.

Lecture 2: Contradiction and InductionMIT OpenCourseWare · MIT 6.1200J, Spring 2024 · 80 min

Root 2 - NumberphileNumberphile · 9 min

• Richard Hammack, Book of Proof, 3rd edition (free PDF): chapter 2 (logic), chapter 4 (direct proof), chapter 5 (contrapositive), chapter 6 (contradiction), chapter 9 (disproof and counterexamples) and chapter 10 (induction).
• Lehman, Leighton and Meyer, Mathematics for Computer Science (free PDF): chapter 1 (proofs) and chapter 5 (induction).
• Daniel Solow's and Daniel Velleman's books (How to Read and Do Proofs, How to Prove It) are good printed guides if your library has them.