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!
Welcome to the World of Proof by Cases!
In your H3 Mathematics journey, you will find that some mathematical statements are like puzzles that change depending on the numbers you use. A rule that works for even numbers might look totally different for odd numbers. This is where Proof by Cases (sometimes called "exhaustion") comes to the rescue!
Think of it as the "Divide and Conquer" strategy. Instead of trying to prove a statement for every single number at once, we break the problem into smaller, manageable groups (cases) and prove each one individually. If we cover every possible scenario, the whole statement must be true!
Don’t worry if this seems tricky at first; once you see the patterns, it becomes one of the most logical tools in your math toolkit.
1. What Exactly is Proof by Cases?
A Proof by Cases consists of showing that a statement \(P\) is true by breaking the domain (the set of numbers we are looking at) into several sub-groups. We then prove that \(P\) is true for each sub-group individually.
The Golden Rule: For the proof to be valid, your cases must be exhaustive. This means they must cover every single possibility. If you leave even one tiny scenario out, the whole proof falls apart!
A Simple Analogy:
Imagine you want to prove that you will always be prepared for the weather tomorrow. You can't just say "I'll wear a coat," because it might be hot. Instead, you break it into cases:
Case 1: It rains. (I will bring an umbrella.)
Case 2: It is sunny. (I will wear sunglasses.)
Case 3: It snows. (I will wear a parka.)
Since it must either rain, be sunny, or snow (assuming these are the only options!), you have proved you are always prepared!
Key Takeaway:
To prove a statement by cases, you must show that the statement holds true for Case 1 OR Case 2 OR Case 3... until all possibilities are exhausted.
2. When Should You Use This?
You should consider using Proof by Cases when a single formula or logical path doesn't apply to everything. Common "triggers" for using cases include:
- Parity: When a statement involves integers that could be even or odd.
- Absolute Values: When you see \( |x| \), because the behavior changes based on whether \( x \) is positive, negative, or zero.
- Inequalities: When the sign of a variable changes the direction of the inequality.
- Remainders (Modular Arithmetic): When a number could leave different remainders when divided by another number (e.g., \( n \equiv 0, 1, \text{ or } 2 \pmod 3 \)).
Did you know?
The famous "Four Color Theorem" (which states that any map can be colored with just four colors so that no two adjacent regions share a color) was proved using 1,482 different cases! It was so complex that a computer had to check all the cases.
3. Step-by-Step Guide to Writing the Proof
Let's look at how to structure your answer to keep it clear for the examiner:
Step 1: State your plan. Tell the reader you are using proof by cases.
Step 2: Define your cases. Make sure they cover everything (e.g., \( n \) is even, \( n \) is odd).
Step 3: Prove Case 1. Use algebra or logic to show the statement is true for this group.
Step 4: Prove Case 2 (and so on). Do the same for the remaining groups.
Step 5: Conclusion. Briefly state that since the statement holds for all possible cases, it is true for all values.
4. A Classic Example: Squares of Integers
The Problem: Prove that for any integer \( n \), the value of \( n^2 + n \) is always even.
Wait! Before we start, let's remember:
An even number can be written as \( 2k \).
An odd number can be written as \( 2k + 1 \).
(Where \( k \) is an integer.)
Case 1: \( n \) is even.
Let \( n = 2k \).
Then \( n^2 + n = (2k)^2 + (2k) = 4k^2 + 2k \).
We can factor out a 2: \( 2(2k^2 + k) \).
Since this is 2 times an integer, the result is even.
Case 2: \( n \) is odd.
Let \( n = 2k + 1 \).
Then \( n^2 + n = (2k + 1)^2 + (2k + 1) \).
Expanding this: \( (4k^2 + 4k + 1) + (2k + 1) = 4k^2 + 6k + 2 \).
Again, factor out a 2: \( 2(2k^2 + 3k + 1) \).
This is also 2 times an integer, so the result is even.
Conclusion: Since \( n \) must be either even or odd, and in both cases \( n^2 + n \) is even, the statement is proved!
Quick Review Box:
Checklist for a solid proof:
1. Are my cases distinct? (They shouldn't overlap unnecessarily, though it's okay if they do, as long as they cover everything).
2. Are my cases exhaustive? (Did I miss the number zero? Did I miss negative numbers?)
3. Did I reach a clear conclusion for every single case?
5. Common Mistakes to Avoid
Even the best students can trip up on these "traps":
- The "Missing Zero" Trap: If you are splitting cases into "positive" and "negative," don't forget the case where \( x = 0 \)!
- Over-complicating: Don't create 10 cases if 2 will do. Look for the simplest way to divide the numbers.
- Not being exhaustive: If you prove something for all prime numbers, you haven't proved it for all integers (you missed 1, 4, 6, 8, etc.).
Memory Trick: "CEO"
To remember what makes a good Proof by Cases, remember CEO:
Cases are defined.
Exhaustive (covers everything).
One-by-one proof.
6. Advanced Tip: Using Modulo
As an H3 student, you are expected to know Modular Arithmetic. This is a powerful way to create cases! If a problem involves divisibility by 3, you can split your proof into three cases based on remainders:
- Case 1: \( n = 3k \) (Remainder 0)
- Case 2: \( n = 3k + 1 \) (Remainder 1)
- Case 3: \( n = 3k + 2 \) (Remainder 2)
This covers every possible integer in the universe because every number leaves a remainder of 0, 1, or 2 when divided by 3!
Summary Takeaway:
Proof by cases is your best friend when a problem feels "split." By breaking the big problem into smaller, simpler logical steps, you can tackle even the most complex H3 theorems with confidence. Just remember: cover all the bases and prove every case!