from Discrete Mathematics & Probability Theory on Sep 17, 2023

How to write a proof

One of the biggest challenges with any proof is: How do I get started? It seems like "know the answer or don't", but the process isn't actually so black and white. There are ways to make forward progress even without fully knowing the answer in advance.

In this post, we'll focus on proofs for discrete mathematics, specifically on tips for those new to proof writing. As an example, we'll use another divisibility proof.

Let's now walk through the thought process.

Be thorough: What parts need to be proved?

At a high level, your first step is to break down this statement into all its component pieces. Depending on the statement and even the proof approach you take, there may be multiple components to keep track of and address. Let's revisit our proof statement from before.

In this example, we have an "if and only if" condition, meaning we have to prove equivalence between two statements:

  1. "An integer is divisible by 4"
  2. "The integer formed by the two rightmost digits are divisible by 4"

Recall that to prove equivalence, we have two options:

  1. Show algebraic equivalence.
  2. Show that both statements imply the other.

We'll keep both options open for now. Just keep the above in mind — we have multiple parts of the proof to complete. Here are a few more different possible parts you may need to address:

  1. "if and only if" or "iff" means equivalence (from above). Prove implication in both directions or algebraic equivalence.
  2. "for all" means there are multiple cases cover. This could be straightforward to understand if the cases are order-able (e.g., "for all integers"). However, you could also introduce arbitrary subproblems yourself, to reduce the problem's complexity. For example, you may prove for odd and even numbers separately.

This culminates in our very first tip, which is to list all the statements you need to prove. This sounds silly, but it's a common mistake — more common than you might think — to leave out a part of the final proof.

Be formal: What do I need to prove?

Not all proofs need this step, but if you're stuck, this is your next goal. Your goal is to formalize the statement. In other words, translate the statement into an expression. There are two specific parts that need translation:

  1. The conditions that the problem provides. These are the subjects of your proof, and the properties that narrow down the pool of subjects. For example, the subjects could be "integers", "graphs" or "players". The properties that need formalizing could be "positive", "bipartite" or "that have won a match".
  2. The objective you're trying to prove — what statement expresses the property you're trying to prove? For example, this could be the "parity of a number" or the "connectedness of a graph".

The above then need to be translated into some form of expression that makes natural language easier to work with. Let's start with the example above, then work towards other ways you may formalize a statement. Here's the proof again.

Funnily enough, since we're proving equivalence, the conditions and the objective are one and the same. In short, we want to formalize the following two statements:

Formalizing statement #1: "An integer is divisible by 4". There are several ways to formalize this statement, and we'll walk through a few.

Formalizing statement #2: "The integer formed by the two rightmost digits are divisible by 4". Ignore the divisibility part, as we've covered that above. Our goal is to somehow express the number formed by the last two digits.

Now we have the above to statements, and our goal is to prove their equivalence, as we summarize below.

$$x = 0 (\textrm{mod } 4) \iff 10 d_1 + d_0 = 0 (\textrm{mod } 4)$$

This now leads us to our next tip, which is to formalize your conditions and objective. Many times, getting "stuck" on a proof can mean being unable to formalize some part of the statement. Finding the right framework to formalize a problem is sometimes non-trivial.

The above formalization is "straightforward" — in the sense that now you've seen it, you'll know how to formalize a divisibility problem next time. However, you may not always want to formalize. When you do, take note of how to formalize. This leads us to our next tip.

Know proof types: What options do I have?

There are plenty of resources online that cover the different possible proof types, so we'll only cover the types briefly here. The below is a "review" of sorts. In short, you have a few different options; here are the most popular ones:

  1. Direct proof: This is what it sounds like. Go straight from step 1 to 2 to 3 to prove your statement.
  2. Proof by contradiction: Say you want to prove a statement is true. Assume the statement is false and show this leads to a contradiction. Critically, remember you're trying to show a contradiction, not disprove the false statement. Ultimately, your proof needs to explicitly show a statement is true and false at the same time.
  3. Proof by induction: For any order-able cases, show all cases hold by proving the base case, making an inductive hypothesis, and proving the inductive step. In other words, prove the case=0 case. Then, show that if case=i is true, case=i+1 is true as well. This ensures that all cases are true. You can optionally use strong induction, where the inductive hypothesis assumes that all cases case=0 up to case=i are true, instead of assuming just case=i is.

Using propositional logic, you can also derive other equivalent proofs, such as proof by contraposition, where you prove $\neg Q \implies \neg P$ instead of the equivalent $P \implies Q$. In other words prove "if leprechauns don't exist, pigs don't fly" instead of proving "if pigs fly, leprechauns exist".

Let's go back to our example from above.

We managed to formalize the statement as the following.

$$x = 0 (\textrm{mod } 4) \iff 10 d_1 + d_0 = 0 (\textrm{mod } 4)$$

To simplify this proof, we can prove a stronger statement. Namely, that in mod-4 space, the two expressions, x and the number formed by the last 2 digits, are exactly the same.

$$x = 10 d_1 + d_0 (\textrm{mod }4)$$

Now, we have our challenge: How do we link our two statements? In most cases, you're linking your conditions to your objective. In this case, we're linking the two statements we're proving equivalence for. To be specific, how do we express the value of our number $x$ as a function of its digits $d_D, d_{D-1}, … d_1, d_0$?

Since our numbers are in base 10, we can re-express $x$ as a function of its digits. This gives us the following.

$$x = \sum_{i=0}^{D-1} 10^i d_i (\textrm{mod }4)$$

This is now the first step of our proof.

Try everything: What can I possibly do?

In short, when you're stuck, you have two options:

  1. Try all the algebra you can: Try all the operations available to you. This can mean expanding quadratic forms, taking inverses, or moving numbers around to simplify an equation.
  2. Apply any conditions you can: Do any of the conditions provided in the original statement apply? If you can use those conditions, try to. The conditions may help you simplify, invert, or otherwise move you forward to an interesting expression.

This leads us to our next tip, which is to try everything available to you, whether algebraically or in the context of the problem — by leveraging conditions in the original statement.

In the above example, let's start back from the expression we've arrived at.

$$x = \sum_{i=0}^{D-1} 10^i d_i (\textrm{mod }4)$$

We're not sure what this tells us, so we try expanding the summation out. This gives us the following.

$$x = 10^D d_D + ... + 100 d_2 + 10 d_1 + d_0 (\textrm{mod }4)$$

The above now reveals something interesting. We notice that every term with a 100 or larger coefficient goes to 0, since they're all multiples of 4.

$$x = \underbrace{10^D d_D + ... + 100 d_2}_{=0} + 10 d_1 + d_0 = 10 d_1 + d_0 (\textrm{mod }4)$$

And at this point, our proof is mostly completed! We would then need one last part: Since the above expressions are equal in mod-4, $x = 10d_1 + d_0$, each statement is divisible by 4 if and only if the other is.

Now, our proof is done.

Conclusion: What is our key realization?

With that said, our work isn't quite done yet. To ensure that you can repeat this process in the future, make sure to keep track of what intuition was needed (or could be used) to solve the problem in a single sentence.

The key idea is this: You'll rarely, if ever, have the intuition for a solution in advance. However, to build that intuition, we can work backwards.

  1. Start with problem-solution pairs, and distill the solutions into a core insight. Slowly, build a library of mappings from insight to problem.
  2. Once that library is big enough, you should be able to start identifying the reverse direction — how to map problems to insights.

This leads us to our final tip here, which is to always distill a solution into its intuition, when learning. This "intuition" is a single sentence, using as few words as possible, to describe the core realization behind your proof.

Take our example above again. This was the original prompt.

Our proof ultimately was a single line of algebra in modular arithmetic, with some explanation at the end.

$$x = \underbrace{10^D d_D + ... + 100 d_2}_{=0} + 10 d_1 + d_0 = 10 d_1 + d_0 (\textrm{mod }4)$$

You can then distill the above one-liner into the following intuition, as the first entry in your library of insights.

Do the same for any problem-solution pair you come across and start building this library of insights. Do the following now, to get started.

Armed with the library of insights and the tips above, you should be much more well-prepared to handle proofs in the wild. If you would like a real-world example of fixing and improving proofs, see How to fix a proof


← back to Discrete Mathematics & Probability Theory