How do you prove that $(a+b)^2=a^2+2ab+b^2$ for all numbers $a$ and $b$? Not by testing values: no amount of examples covers all numbers. You prove it by writing a chain:

$$\begin{aligned} (a+b)^2&=(a+b)(a+b)\\ &=a(a+b)+b(a+b)\\ &=a^2+ab+ba+b^2\\ &=a^2+2ab+b^2. \end{aligned}$$

Each equals sign links two neighbours, and each link is guaranteed by a known rule: the definition of the square, the distributive law, the distributive law again, the commutativity of multiplication. By transitivity, Euclid’s law that text 1 presented, the first link equals the last. The proof is the chain.

A chain with labels

In ordinary writing, the justifications stay in the writer’s head. The reader has to guess why each equals sign holds. In the 1980s, the Dutch computer scientist Edsger Dijkstra and his colleague Wim Feijen proposed a format in which each link carries its own label, in braces:

$$\begin{aligned} &(a+b)^2\\ =\;&\{\text{definition of square}\}\\ &(a+b)(a+b)\\ =\;&\{\text{distributive law}\}\\ &a(a+b)+b(a+b)\\ =\;&\{\text{distributive law}\}\\ &a^2+ab+ba+b^2\\ =\;&\{\text{commutativity: }ba=ab\}\\ &a^2+2ab+b^2 \end{aligned}$$

The format takes up more space and says more. Each line of expression alternates with a line of justification, and the equals sign sits on the left margin, in plain view, as the link in the chain that it really is. Dijkstra called this style calculational proof: proving is calculating, and calculating is replacing equals by equals with the rule on display.

Which side to start from

A practical rule for proving identities: start from the more complicated side. Simplifying is easier than guessing how to complicate. To prove

$$\frac1k-\frac1{k+1}=\frac1{k(k+1)},$$

you start on the left, which has two fractions and asks to be combined:

$$\begin{aligned} \frac1k-\frac1{k+1}&=\frac{k+1}{k(k+1)}-\frac{k}{k(k+1)}\\ &=\frac{(k+1)-k}{k(k+1)}=\frac1{k(k+1)}. \end{aligned}$$

Starting on the right would require knowing in advance that $1=(k+1)-k$ is a good idea. The proof from the left discovers it along the way.

The mistake of starting from the end

There is a way of going wrong that looks like a proof. A student wants to show that $-1=1$ and writes:

$$-1=1\quad\Longrightarrow\quad(-1)^2=1^2\quad\Longrightarrow\quad1=1.$$

“I arrived at something true, so the first line is true.” It is not. A chain of $\Rightarrow$ that starts from a false sentence can arrive at a true one; this is what the previous text called a step that gains solutions. Starting from what you want to prove and arriving at $1=1$ or $0=0$ only proves something if every step is $\Leftrightarrow$, and then it would be better to write the chain in the right order, from the known to the unknown.

Exercise: a chain with labels

Prove that $(a-b)(a+b)=a^2-b^2$ in Dijkstra’s format.

$$\begin{aligned} &(a-b)(a+b)\\ =\;&\{\text{distributive law}\}\\ &a(a+b)-b(a+b)\\ =\;&\{\text{distributive law}\}\\ &a^2+ab-ba-b^2\\ =\;&\{\text{commutativity: }ba=ab\text{, and }ab-ab=0\}\\ &a^2-b^2 \end{aligned}$$
Exercise: where is the mistake? (4 = 5)
$$\begin{aligned} -20&=-20\\ 16-36&=25-45\\ 16-36+\tfrac{81}4&=25-45+\tfrac{81}4\\ \left(4-\tfrac92\right)^2&=\left(5-\tfrac92\right)^2\\ 4-\tfrac92&=5-\tfrac92\\ 4&=5 \end{aligned}$$

The first four lines are right: both sides of the fourth equal $\frac14$. The mistake is taking the square root. From $x^2=y^2$ follows $x=y$ or $x=-y$, and here $4-\frac92=-\frac12$ and $5-\frac92=\frac12$: the second option holds, not the first. It is the same squaring step, read backwards.

Chapter index · ← ⇒ and ⇔: what is gained and what is lost when an equation is transformed · The words of a proof: let, suppose, hence, ∎ →