Finding the Right Lemma

When a Proof Needs a Bridge

In the previous tutorial, “Disproving Universal Statements,” the goal was to find one input that makes a universal claim fail. Proving a universal statement asks for a different kind of organization: we must show that the claim holds for every permitted input. Sometimes the route from the hypothesis to the conclusion is immediate. Often, however, a direct attempt leaves a gap. A useful response is to prove an intermediate statement that makes the connection easier to see.

For example, suppose we want to prove that an integer with an even square must itself be even. The hypothesis concerns a square, but the conclusion concerns the integer. A helpful intermediate fact goes in the other direction: the square of an odd integer is odd. Once that fact is established, an odd integer cannot have an even square. The intermediate fact is the key that connects the form of the hypothesis to the desired conclusion.

Definition: A lemma is a mathematical statement proved as an aid to establishing another result. A lemma can be useful because it supplies a missing implication, simplifies an expression, or isolates a recurring calculation. Its name describes its role in an argument; it does not mean the statement is less important or less difficult than a theorem.

A lemma is not a guess to insert whenever a proof feels difficult. It must be true, it must be proved, and it must actually help establish the goal. The central planning question is: What fact, if I knew it, would let me move from the given information to the conclusion? Sometimes the answer is a new statement. Sometimes it is an algebraic identity or a simple sign observation that can be proved in a few lines.

The Lemma-Bridge Principle

The basic structure is simple. Suppose the hypothesis is \(P\), the desired conclusion is \(Q\), and a proposed lemma is \(R\). If the hypothesis implies the lemma, and the lemma implies the conclusion, then the desired implication follows. The lemma is a bridge: it divides one difficult-looking move into two justified moves.

Theorem (Lemma-Bridge Principle). Let \(P\), \(Q\), and \(R\) be statements. If \(P\) implies \(R\) and \(R\) implies \(Q\), then \(P\) implies \(Q\).

Proof. Suppose \(P\) is true. Since \(P\) implies \(R\), the statement \(R\) is true. Since \(R\) implies \(Q\), it follows that \(Q\) is true. Thus whenever \(P\) is true, \(Q\) is true, which is exactly the assertion that \(P\) implies \(Q\). \(\square\)

In a written proof, the bridge may not appear as a separate, formally titled lemma. It could be a sentence within the proof. Giving it a name is especially useful when the fact will be reused, when its proof takes several steps, or when separating it from the main argument makes both parts easier to follow.

A candidate lemma should pass two checks. First, can it be proved from accepted facts and the problem’s assumptions? Second, once proved, does it genuinely advance the argument? A statement that merely repeats the goal in different words is not a helpful bridge. Nor is a true statement enough if there is no clear way to use it.

Worked Examples: Finding a Useful Intermediate Fact

Worked Example: An Even Square Forces an Even Integer

We will prove that if \(n\) is an integer and \(n^2\) is even, then \(n\) is even. Directly starting with \(n^2\) being even does not immediately give a representation of \(n\). Instead, look for a fact that rules out the alternative: prove that an odd integer has an odd square.

Lemma. If \(n\) is an odd integer, then \(n^2\) is odd.

Proof of the lemma. Since \(n\) is odd, there is an integer \(k\) such that \(n=2k+1\). Squaring and rearranging gives

$$ n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1. $$

Because \(k\) is an integer, \(2k^2+2k\) is an integer. The final expression is therefore of the form twice an integer plus one, so \(n^2\) is odd. This proves the lemma.

Now suppose \(n^2\) is even. If \(n\) were odd, the lemma would imply that \(n^2\) is odd, contradicting the assumption that it is even. Every integer is either even or odd, so \(n\) must be even. The lemma was useful because it converted the possibility that \(n\) is odd into a contradiction with the given information.

This example illustrates a common planning move: when a direct proof stalls, test whether proving the claim by contradiction or contrapositive gives a more convenient target. Here, it was easier to describe an odd integer as \(2k+1\) and calculate its square than to begin with an arbitrary even square and extract information about its root.

Worked Example: A Product of Consecutive Integers Is Even

We will prove that \(n(n+1)\) is even for every integer \(n\). The expression is a product, so a useful intermediate fact is that at least one of its two consecutive factors is even. Check the two parity cases for \(n\).

Lemma. For every integer \(n\), at least one of \(n\) and \(n+1\) is even.

Proof of the lemma. If \(n\) is even, then \(n\) is already an even factor. If \(n\) is odd, write \(n=2k+1\) for some integer \(k\). Then

$$ n+1=(2k+1)+1=2(k+1), $$

which is even. These cases cover every integer \(n\), so at least one of \(n\) and \(n+1\) is even.

Proof of the claim. By the lemma, either \(n=2k\) for some integer \(k\), or \(n+1=2j\) for some integer \(j\). In the first case,

n(n+1)=(2k)(n+1)=2\bigl(k(n+1)\bigr),

which is even because \(k(n+1)\) is an integer. In the second case,

$$ n(n+1)=n(2j)=2(nj), $$

which is also even because \(nj\) is an integer. Thus \(n(n+1)\) is even in either case. The lemma isolated the only fact needed to finish: one factor of the product is even.

Notice how the form of the goal helped suggest the lemma. To show that a product is even, look for an even factor. To show that a sum has a particular parity, look for useful representations of its summands. This does not mean there is only one possible lemma; it means the desired conclusion can guide the search for a manageable intermediate step.

Worked Example: Comparing Squares Using a Factorization Lemma

Let \(x,y\) be real numbers with \(0\leq x\leq y\). We want to prove that \(x^2\leq y^2\). Rather than compare the squares directly, use the lemma that the difference of squares factors:

$$ y^2-x^2=(y-x)(y+x). $$

Proof of the lemma. Expanding the right-hand side gives

$$ (y-x)(y+x)=y^2+xy-xy-x^2=y^2-x^2. $$

So the identity holds. To use it, note that \(y-x\geq0\) because \(x\leq y\), and \(y+x\geq0\) because \(x\geq0\) and \(y\geq0\). The product of two nonnegative real numbers is nonnegative. Therefore,

y^2-x^2=(y-x)(y+x)\geq0.

Rearranging this inequality gives \(x^2\leq y^2\), as required. The factorization lemma made the order assumptions visible as signs of factors. Without it, the comparison of squares might look like an unsupported appeal to the idea that squaring preserves order; the factorization supplies a direct justification under the stated hypotheses.

How to Choose and Use a Lemma

The examples used different clues. In the square-parity proof, the conclusion concerned whether an integer was even, so the useful lemma described what happens to the square of an odd integer. In the consecutive-product proof, the goal concerned a product, so the lemma identified an even factor. In the inequality proof, the obstacle was comparing two squares, so the factorization turned their difference into a product whose signs could be checked.

A practical search can proceed in stages:

State the gap.
Identify what the assumptions give you and what the conclusion requires. Be specific about the step you cannot yet justify.

Work backward from the goal.
Ask what fact would make the conclusion follow. For a product, this may be a factor with a useful property; for an inequality, it may be a factorization or sign estimate.

Check the proposed bridge.
Make sure the assumptions imply the lemma and that the lemma really helps establish the goal. If either link is missing, refine the proposed statement.

Prove and apply it clearly.
Give a complete justification of the lemma, then explicitly explain how it yields the desired conclusion.

One common pitfall is to announce a useful-looking fact without proving it. Calling a statement a lemma does not make it established. Another is to prove a lemma that is stronger than necessary and harder than the original problem. Prefer the simplest intermediate fact that closes the gap. A third pitfall is to prove the lemma correctly but never connect it back to the goal. The argument needs both links: the assumptions lead to the lemma, and the lemma leads to the conclusion.

A proof can also contain several bridges. If the needed route is \(P\) to \(R\), then \(R\) to \(S\), then \(S\) to \(Q\), each step must be justified. That is not a defect: breaking a complicated argument into smaller verified steps often makes it more reliable. The Lemma-Bridge Principle explains why the chain works, while the proof itself should make the intermediate steps clear enough to check.

Finding a lemma is therefore a method of organizing thought, not a special trick reserved for difficult theorems. Look at the shape of the goal, identify what would make it follow, and test whether that intermediate fact can be proved from what is already known. When the bridge is well chosen, the main argument becomes shorter and its logic easier to see.

Check Your Understanding

For each question, focus on how an intermediate statement contributes to a proof.

What two implications make a proposed statement \(R\) a valid bridge from a hypothesis \(P\) to a conclusion \(Q\)?
In the proof about an even square, why was it useful to establish that an odd integer has an odd square?
What feature of \(n(n+1)\) suggested looking for a lemma about the parity of its factors?
In the comparison of \(x^2\) and \(y^2\), which signs were needed after factoring the difference?
Why is it not enough to state a useful intermediate fact without proving it or connecting it to the goal?

What You'll Learn