Welcome to Proof by Construction!

In your H2 Mathematics journey, you’ve spent a lot of time calculating and solving. In H3 Mathematics, we take a step back and ask: "How do we know this thing even exists in the first place?"

Proof by construction is one of the most satisfying ways to answer that question. Think of it like a "recipe." Instead of just arguing that a cake could exist, you actually bake the cake and put it on the table. If you can build it, it must be real! This chapter will teach you how to be a mathematical architect.

1. What is Proof by Construction?

In mathematics, we often encounter statements that start with "There exists..." (represented by the symbol \(\exists\)). To prove these statements, we use a constructive proof.

A Proof by Construction proves the existence of a mathematical object by creating it or providing a specific method (an algorithm) to find it.

The Core Idea: To prove "There exists an \(x\) such that \(P(x)\) is true," you simply need to find one specific value of \(x\) and show that it satisfies the condition \(P(x)\).

Analogy: The Treasure Hunt

Imagine someone says, "There is a gold coin hidden in this park."
• A non-constructive proof might argue: "The metal detector is beeping, so there must be gold somewhere."
• A constructive proof says: "I dug at these coordinates (x, y) and here is the coin."

Key Takeaway:

If you find one example that works, the "existence" is proven. You don't need to find every example—just one is enough!

2. The Three-Step Process

Don't worry if this seems a bit abstract at first. You can follow these three simple steps for almost any proof by construction:

Step 1: Identify the "Target." Look at the statement and figure out exactly what kind of object you need to find (a number? a function? a set?).

Step 2: "Construct" the Candidate. Use your intuition, rough work, or trial and error to pick a specific candidate. (Note: You don't usually show your trial and error in the final proof!)

Step 3: Verify. Show step-by-step that your chosen candidate actually meets all the requirements stated in the problem.

3. Examples in Action

Example 1: Number Theory (The Basics)

Prove that there exists an even prime number.

Construction: Let \(n = 2\).
Verification:
1. Is \(n\) even? Yes, \(2 \div 2 = 1\), so it is even.
2. Is \(n\) prime? Yes, the only factors of 2 are 1 and itself.
Since we have found a number that is both even and prime, the statement is proven. Q.E.D.

Example 2: Composite Numbers

Prove that there exists an integer \(n\) such that \(2^n - 1\) is a composite number, where \(n > 1\).

Construction: Let's try some values.
If \(n=2\), \(2^2 - 1 = 3\) (Prime).
If \(n=3\), \(2^3 - 1 = 7\) (Prime).
If \(n=4\), \(2^4 - 1 = 15\) (Composite!).
So, we choose \(n = 4\).
Verification: When \(n = 4\), \(2^4 - 1 = 15\). Since \(15 = 3 \times 5\), it is composite. The existence is proven.

Quick Review: Notice that in Example 2, we didn't have to talk about \(n=5\) or \(n=6\). Once we found \(n=4\), our job was done!

4. Constructive vs. Non-Constructive Proofs

In H3 Mathematics, it is important to know that not all existence proofs are constructive.

• Constructive: "Here is the number \(x = 5\). See? It works!"
• Non-Constructive: "If there weren't such a number, logic would break, so one must exist... but I have no idea what it is."

Did you know? Constructive proofs are highly valued in Computer Science. If you can "construct" a solution, you can write a program to find it. Non-constructive proofs tell a computer "it's there," but give the computer no instructions on how to find it!

5. Common Pitfalls and Tips

Common Mistake: Proving for "All" instead of "One"

Students sometimes try to prove that a property holds for all numbers in a set when the question only asks to prove that at least one exists.
Tip: If the question says "There exists..." or "Show that there is...", just find one specific example. Don't make the math harder than it needs to be!

Common Mistake: Forgetting Verification

It is not enough to just state the example. You must show the math that proves your example works.
Tip: Always end your proof by clearly showing how your chosen value fits the original definition given in the question.

Memory Aid: The "ID Card" Trick

Think of Proof by Construction like checking someone's ID.
1. The question asks for someone of a certain age.
2. You bring a person forward.
3. You show their ID card (the calculation) to prove they are that age.

6. Summary Checklist

When tackling a Proof by Construction question, ask yourself:

  • Did I identify the existence quantifier (\(\exists\))?
  • Did I clearly state my chosen candidate?
  • Did I show the calculations to verify it meets the criteria?
  • Is my example within the domain specified (e.g., is it an integer if the question asks for an integer)?

Keep going! Proof by construction is all about creativity. If a proof feels like it's getting too complicated, take a breath and try testing some simple numbers. Often, the "construction" is simpler than you think!