from Discrete Mathematics & Probability Theory on Sep 10, 2023

How to fix a proof

One of the most pressing questions when you begin writing proofs is: What makes a proof, a proof? It's tough to know when a proof is lacking detail and when enough is enough.

In this post, we'll walk through proving a seemingly obvious statement — except, instead of jumping to the solution, we'll walk through the process of building a proof, from the ground up. We'll cover pretty much every possible proof, and for each path, we'll show how insufficient proofs can be revised to make complete proofs.

For more real-world applicability to your own work, we'll use a statement that is "obvious" to make a point.

We know that 5 is one of the easiest numbers to check divisibility for, and we use this rule all the time. With that said, how do we prove such a statement is true?

Wrong proofs by ChatGPT

Let's start with some incorrect proofs that ChatGPT provides. I've included my first few attempts to get a solid proof from ChatGPT below; these mistakes are fairly obvious because it makes obviously wrong conclusions:

However, not all proofs are this obviously wrong. I've paraphrased one of ChatGPT's better proofs down below. Can you tell what's wrong? There are two mistakes: one subtle and one even more subtle.

Here's the original chat and proof: https://chat.openai.com/share/a808e4ce-fc4d-4000-bd1c-cb5dcc65e173, and here are the mistakes I tried to get ChatGPT to fix. We'll discuss these in more detail down below.

  1. Applying inductive hypothesis: The first subtle error is in how the inductive hypothesis is applied. The number 10k used in the inductive step is actually itself a (k+1)-digit number, which we can't assume is divisible by 5 if it ends in 0. This (k+1) case is what we're trying to prove after all.
  2. What to induct over: The second subtle-r error is that this proof assumes the sequence generated by the formula $x_i = 5i, i \in \mathcal{Z}$ actually covers all numbers ending in 0 or 5. This can of course be proven, but it can't be assumed. We need to start from the statement "all numbers ending in 0 or 5" instead.

The above mistakes are not atypical however. Take any practice exam, or sets of homeworks, and you'll likely find similarly subtle errors in your own proofs. What's more, the above proof seems "easy", which leaves us to wonder: How many of these mistakes pervade our answers for "harder" proofs? To answer that, let's now see how to fix these mistakes.

How to prove the "obvious"

As a quick sanity check, we run through every number that ends in 0 or 5: 0, 5, 10, 15, 20 etc. We know they all are divisible by 5, so the statement appears to check out. We try to translate this into a statement reflecting this.

There are two problems here:

  1. Reread the original prompt and the "proof" above. The two sentences are identical. This is what we call "begging the question" — I just rewrote the problem statement again.
  2. More importantly, we only checked a few numbers. How do we know some crazy large number ending in 5 or 0 isn't actually divisible by 5?

One way to make forward progress is to define some terms.

We need to know both

Let's rewrite the proof now using these definitions.

This is looking a lot more legitimate, after we formalized the objective. Formalizing just means we can express the objective in math, so we know what expression to show is true.

Unfortunately, that's all we've done so far: express the what to show and the conditions we have in math. We haven't actually connected the two. There are several ways to do this, and we'll show the thought process for each.

Proof by induction #1

There are two ways to prove by induction.

One approach is to induct over the sequence of all numbers ending in 0 or 5. This is actually trickier than it first seems, due to a small caveat. We'll go over this next. Let's instead cover a simpler proof.

Our first approach here is to induct over the numbers of digits. First show this holds for 1-digit numbers, then 2-digit numbers, then 3-digit numbers etc.

Now we're stuck. We know the digits of the number are $d_i$, we know that $d_0 \in \{0, 5\}$, and we know we need to show the value of our number $x$ can be expressed as $x = 5a, a \in \mathcal{Z}$. What do we even do for the next step?

We need to know the crux of the issue: We have the digits but we need to link the digits to the value.

To fix this, we can express the number's value $x$ in terms of its digits, $d_D, d_{D-1}, …, d_0$.

$$x = 10^{D} d_{D} + 10^{D-1} d_{D-1} + ... 10 d_1 + d_0$$

This is moving in the right direction! Here, we're stuck again. However, notice we haven't used the condition provided: That if the D-digit number ends in 0 or 5, it is divisible by 5. To use this, we need to extract a D-digit number from the above that we know always ends in 0 or 5.

To do this, simply take the last D digits.

$$x = 10^{D} d_{D} + (\underbrace{10^{D-1} d_{D-1} + ... 10d_1 + d_0}_{\textrm{D-digit number}})$$

Notice the last D digits end in a 0 or 5, since we said that $d_0 \in \{0, 5\}$. As a result, the last D digits are divisible by 5 and can be expressed as $5a, a \in \mathcal{Z}$.

There are several other options for extracting D-digit numbers that don't end in 0 or 5. As a result, you would hit a wall, because you wouldn't be able to apply your inductive hypothesis:

But now, how do we deal with the first term? The first term is a (D+1)-digit number.

The first term requires a trick: It's a (D+1)-digit number, but we can factor a 10 to make it a D-digit number. In particular, this produces a D-digit number that ends in 0, so is divisible by 5 and can be expressed as $5b, b \in \mathcal{Z}$.

$$10 (10^{D-1} d_{D}) = 10(5b)$$

Now, we can rewrite our full expression for our original number's value to be

$$x = 10(5b) + 5a = 5(10b + a) = 5c$$

Again, $c = 10b + a$ is another integer, so $x$ is now divisible by 5. We can now use the above to complete our proof.

This is sort of wordy, so let's see if strong induction can improve this.

Proof by strong induction

Let's start with the expanded assumption that all smaller numbers, ending in 0 or 5, are divisible by 5.

Let's start over from our full expression for $x$.

$$x = 10^D d_D + 10^{D-1} d_{D-1} + ... 100 d_2 + 10 d_1 + d_0$$

We'll now analyze this term by term.

The first term requires the same trick from above: It's a (D+1)-digit number, but we can factor a 10 to make it a D-digit number.

$$10^D d_D = 10 (\underbrace{10^{D-1} d_{D}}_{\textrm{D-digit number}}) = 10(5a) = 5(10a) = 5a_D$$

Using the same trick, we've shown that the first term is divisible by 5. As a result, all terms in $x$ are divisible by 5.

$$x = 5a_D + 5a_{D-1} + ... + 5a_2 + 5a_1 + 5a_0$$

We can then factor out the 5. Since the $a_i$ are all integers, we can replace their sum with one integer $b$, to get $x = 5b, b \in \mathcal{Z}$. This finally shows that our (D+1)-digit number is divisible by 5. Let's complete our proof.

This didn't necessarily simplify our proof, but we've re-proved the statement using a slightly different technique.

Proof by induction #2

Let's now try to induct over the sequence of all numbers ending in 0 or 5. This is the sequence 0, 5, 10, 15, 20, 25 etc. One way to get this sequence is to use the formula $x_i = 5i$ where $i \in \mathcal{Z}$. Well, knowing how this sequence is generated, it seems trivial to prove this right?

However, there's a catch. We would also need to show that this formula — and this sequence — covers all possible values that end in 0 or 5. What if some magically large number ending in 0 or 5 isn't covered? We've only checked that the first 6 values are. So, the bulk of our proof is going to prove this auxiliary statement, which we'll call our "lemma".

Notice that this auxiliary statement is very similar to the original proof, but it's not the same. We'll comment on this more later. Funnily enough, we've now landed ourselves a slightly tougher proof, but let's continue with this anyways.

Let's show brief proofs using any of the techniques we mentioned that are viable.

You could then use the above to write a proof by induction. Since all numbers ending in 0 or 5 are accounted for by the sequence, we can iterate over the sequence generated by the formula $x_i = 5i$.

You'll notice above the inductive step is weirdly circular. In the first half, I broke down the parenthetical expression to use the inductive step. In the second half, I fit to the algebraic form that satisfies divisibility, but those two are the one and the same!

The above is the "pedantic" way to do it: In the above proof, I need to distinguish between the formula and the expression for divisibility. However, it's really silly and redundant, so this suggests we don't need induction.

Direct proof

A much simpler method would be to use the lemma you just proved, to write a direct proof. This is the lemma you proved.

Notice this lemma alone doesn't yet complete our original proof.

It states that a particular formula generates all values ending in 0 or 5, but it doesn't say anything about divisibility. Here is the finished proof.

You could also abbreviate the above direct proof by proving the statement directly, skipping the lemma entirely.

Proving Equivalence

Let's say we modify the original statement to prove. Can you spot the difference?

This is very similar to the original statement, except for one critical difference — "if and only if". Here was the original statement, for comparison.

The above "if and only if" now means we need to prove the opposite direction too. We also now need to prove the following.

Since this post is getting long, let's prove this using quick proof by contradiction.

This proves the opposite direction, proving both directions in the "if and only if" statement. However, we can simplify the above, proving both directions at once.

Finally, we can simplify even further by using modular arithmetic to show both directions at once.

The above is a bit dense, but basically, if we mod by 5, all the terms except the last go to 0, because they're all multiplied by 10. The last digit $0 \leq d_0 \leq 9$ needs to then take on a multiple of 5 to be equal to 0 in mod-5 space. In this case, the only possibilities are 0 and 5.

Takeaways

The above completes our full guide to proving the "obvious" divisibility-by-5 statement. There were a large number of twists and turns, and we ended up with a super short single-liner proof. However, the key part is all the different paths you could take, as well as the caveats that each path needed to complete the proof.

Even for such a simple statement, the takeaway is proof-writing is real tricky. What makes a proof valid is more than just definitions and following the steps needed for each proof type. There's an extra element of "what have you proved, exactly?" that needs to be asked and answered, every step of the way.

Knowing which tricky parts to be aware of takes time. However, knowing what to prove can be fixed with some structure. We cover this in our next post, How to write a proof.


← back to Discrete Mathematics & Probability Theory