Proof Writing

This appendix collects some general advice on how to write proofs and derivations. The goal of a proof is not just to convince yourself that a result is true; it is to convince a reader, and to show them why it is true. The principles below all serve that goal.

1 Don’t skip steps

Show every step of the derivation. Each line should follow from the previous line by a single, identifiable move: applying a definition, substituting a known result, or performing one algebraic operation.

When you skip steps, you force the reader to reconstruct your reasoning, which is exactly the work the proof was supposed to do for them. A step that feels “obvious” while you are writing it is often the step a reader gets stuck on. Phrases like “it can be shown that” or “clearly” are usually a sign that a step is being skipped; prefer to show it instead.

2 Annotate each step

For each step, note the definition, theorem, or algebraic rule that justifies it. A brief annotation to the right of the line is usually enough. This makes the proof checkable, and it teaches the reader which tool to reach for in similar situations.

For example, here is a derivation of the identity \(\operatorname{Var}\mathopen{}\left(X\right)\mathclose{} = \operatorname{E}\mathopen{}\left[X^2\right]\mathclose{} - \mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{}\), with each step annotated:

\[ \begin{aligned} \operatorname{Var}\mathopen{}\left(X\right)\mathclose{} &= \operatorname{E}\mathopen{}\left[\mathopen{}\left(X - \operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{}\right]\mathclose{} && \text{(definition of variance)} \\ &= \operatorname{E}\mathopen{}\left[X^2 - 2 X \operatorname{E}\mathopen{}\left[X\right]\mathclose{} + \mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{}\right]\mathclose{} && \text{(expand the square)} \\ &= \operatorname{E}\mathopen{}\left[X^2\right]\mathclose{} - \operatorname{E}\mathopen{}\left[2 X \operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right]\mathclose{} + \operatorname{E}\mathopen{}\left[\mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{}\right]\mathclose{} && \text{(linearity of expectation)} \\ &= \operatorname{E}\mathopen{}\left[X^2\right]\mathclose{} - 2 \operatorname{E}\mathopen{}\left[X\right]\mathclose{} \operatorname{E}\mathopen{}\left[X\right]\mathclose{} + \mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{} && \text{(}\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\text{ is a constant)} \\ &= \operatorname{E}\mathopen{}\left[X^2\right]\mathclose{} - 2 \mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{} + \mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{} && \text{(}\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\operatorname{E}\mathopen{}\left[X\right]\mathclose{} = \mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{}\text{)} \\ &= \operatorname{E}\mathopen{}\left[X^2\right]\mathclose{} - \mathopen{}\left(\operatorname{E}\mathopen{}\left[X\right]\mathclose{}\right)^2\mathclose{} && \text{(collect like terms)} \end{aligned} \]

3 Follow the golden rule

In general, follow the golden rule: treat your readers the way you want to be treated as a reader.

When you read someone else’s proof, you want to be able to follow every step without guessing, to know which result is being used at each line, and to never be left wondering where a quantity came from. Write your own proofs to meet that same standard.