Revision sheet: writing a mathematical proof (201-N11)

If the hypothesis translates at once into an equation ($n=2k$, $b=ak$) → direct proof: start from $P$ and compute until you reach the DEFINITION of $Q$

Example: if $a \mid b$ and $a \mid c$, then $a \mid (bu+cv)$, because $bu+cv=a(ku+lv)$

a FRESH letter for each object you know nothing about: $b=ak$ and $c=al$, never $k$ twice

If the conclusion is a negation, an OR, or is about $n$ while the hypothesis is about $3n+2$ → contrapositive: assume $\lnot Q$ and aim for $\lnot P$

Example: if $3n+2$ is odd then $n$ is odd: start from $n=2k$

the criterion is RICHNESS: prove starting from the richer of the two, the hypothesis or the negation of the conclusion

If the statement contains there is no, none, at most one, is unique, is irrational, is impossible → contradiction: assume $P$ AND $\lnot Q$, and look for any contradiction

Example: $\sqrt{2}$ is irrational; $\log_{2} 3$ is irrational; there are infinitely many prime numbers

these words designate a proposition whose NEGATION is an existence, hence a rich hypothesis: you can name the object and compute with it

If the statement is indexed by an integer $n$, and rank $n+1$ follows from rank $n$ by a small computation → induction: base case, inductive step, conclusion

Example: for all $n \geq 0$, $7^{n}-1$ is divisible by 6, because $7^{n+1}-1=7(7^{n}-1)+6$

induction is not compulsory just because a statement is about all integers: $1+3+\cdots+(2n-1)=n^{2}$ is proved in one line by regrouping

If the statement claims that two objects coincide, or that a value repeats, without asking which → pigeonhole principle: name the objects, name the boxes, count both

Example: among 13 integers, two have the same remainder modulo 12

simple form if you want two objects, generalized form with $\lceil m/n \rceil$ if you want more

If the statement is universal and you suspect it is FALSE → counterexample: a single value, checked against the hypothesis AND the conclusion

Example: $F_{5}=4{,}294{,}967{,}297=641\times 6{,}700{,}417$ disproves “every Fermat number is prime”

it is the only case where a numerical value on its own constitutes a complete proof

If the domain splits naturally: even or odd, remainders modulo $n$, sign → proof by cases, set up INSIDE one of the structures above

Example: $n^{2} \equiv 0$ or $1 \pmod 4$, so no $4k+3$ is a perfect square

the list must be EXHAUSTIVE; it does not need to be disjoint, an overlap costs nothing

If the conclusion is “$A$ or $B$” → negate as “$\lnot A$ AND $\lnot B$”

Example: the negation of “$x>31$ or $y>31$” is “$x \leq 31$ and $y \leq 31$”

If the conclusion is “$A$ and $B$” → negate as “$\lnot A$ OR $\lnot B$”

Example: the negation of “$n$ even and $n>4$” is “$n$ odd or $n \leq 4$”

If the conclusion is an implication “if $A$ then $B$” → negate as “$A$ AND $\lnot B$”, which is no longer an implication

Example: $\lnot(P \Rightarrow Q) = P \land \lnot Q$, and never $P \Rightarrow \lnot Q$

a test that writes “suppose, for the sake of contradiction, that $P$ implies not $Q$” has already lost the question

If the conclusion is “for all $x$, $P(x)$” → negate as “there exists $x$ such that $\lnot P(x)$”: that is exactly a counterexample

Example: negating “every $F_{k}$ is prime” gives “some $F_{k}$ is composite”, and $F_{5}$ is

If the conclusion is “there exists $x$ such that $P(x)$” → negate as “for all $x$, $\lnot P(x)$”, which gives a uniform UPPER BOUND

Example: negating “some box contains 2 objects” gives “each box contains at most 1”, hence a total $\leq n$