🎭 The Detective’s Toolkit: Proof Techniques in Number Theory

Imagine you’re a detective. Your job? Proving things are TRUE beyond any doubt. Today, you’ll learn the secret tools that mathematicians use to solve mysteries about numbers!

🌟 The Big Picture

Think of proof techniques like different tools in a detective’s toolkit:

• Well-Ordering Principle → “Find the smallest suspect”
• Mathematical Induction → “Domino chain reaction”
• Strong Induction → “Use ALL past clues”
• Infinite Descent → “The impossible shrinking trick”
• Pigeonhole Principle → “Too many pigeons, not enough holes”
• Irrationality Proofs → “Proof by contradiction”

Let’s explore each one through stories!

🔍 1. Well-Ordering Principle

The Story

Imagine a classroom where every student has a different number of candies. The teacher says: “Will the student with the FEWEST candies please stand up?”

Can someone always stand up? YES!

This is the Well-Ordering Principle: Every non-empty set of positive integers has a smallest element.

Why It Matters

It sounds obvious, but it’s POWERFUL. Here’s how detectives use it:

The Crime: Someone claims there’s a positive integer that can’t be written as a sum of ones.

The Detective Work:

1. Assume such “bad” numbers exist
2. By Well-Ordering, find the SMALLEST bad number (call it n)
3. But wait… n-1 is smaller, so it CAN be written with ones
4. Just add one more 1 to get n!
5. Contradiction! No bad numbers exist.

Simple Example

Prove: Every positive integer ≥ 2 has a prime divisor.

Proof:

1. Take any n ≥ 2
2. Look at all divisors of n that are ≥ 2
3. This set is non-empty (n itself is there!)
4. By Well-Ordering, pick the SMALLEST divisor, call it p
5. p must be prime! (If p = a×b with a,b < p, then a divides n too, contradicting “smallest”)

✨ Magic: We found a prime without searching—just by trusting that a smallest one exists!

🎲 2. Mathematical Induction

The Story

Picture a row of dominoes. You know two things:

1. The first domino falls (Base Case)
2. If any domino falls, it knocks down the next one (Inductive Step)

What happens? ALL dominoes fall!

graph TD
    A["🁡 Domino 1 Falls<br>#40;Base Case#41;"] --> B["🁡 Domino 2 Falls"]
    B --> C["🁡 Domino 3 Falls"]
    C --> D["🁡 ... All Fall!"]

The Recipe

To prove something is true for ALL positive integers:

1. Base Case: Show it’s true for n = 1
2. Inductive Step: Assume it’s true for n = k, then prove it’s true for n = k+1

Simple Example

Prove: 1 + 2 + 3 + … + n = n(n+1)/2

Base Case (n = 1):

• Left side: 1
• Right side: 1(1+1)/2 = 1 ✓

Inductive Step:

• Assume: 1 + 2 + … + k = k(k+1)/2
• Prove: 1 + 2 + … + k + (k+1) = (k+1)(k+2)/2

Proof:

1 + 2 + ... + k + (k+1)
= k(k+1)/2 + (k+1)      [by assumption]
= k(k+1)/2 + 2(k+1)/2   [common denominator]
= (k+1)(k+2)/2          [factor out (k+1)]

Done! 🎉

💪 3. Strong Induction

The Story

Regular induction is like climbing stairs one step at a time. Strong induction is like having a jetpack—you can use ALL the steps below you, not just the last one!

The Difference

• Regular Induction: Assume P(k) is true, prove P(k+1)
• Strong Induction: Assume P(1), P(2), …, P(k) are ALL true, prove P(k+1)

When to Use It

Use strong induction when proving P(k+1) needs information from MORE than just P(k).

Simple Example

Prove: Every integer n ≥ 2 can be written as a product of primes.

Base Case (n = 2): 2 is prime. So 2 = 2 ✓

Strong Inductive Step:

• Assume: Every integer from 2 to k can be written as a product of primes
• Prove: k+1 can too

Proof:

• Case 1: k+1 is prime → Done! It’s a product of one prime.
• Case 2: k+1 is composite → k+1 = a × b where 2 ≤ a, b ≤ k
  • By strong assumption, both a and b are products of primes
  • So k+1 = (primes from a) × (primes from b) ✓

🎯 Key insight: We needed info about a and b, which could be ANY numbers less than k+1, not just k!

🌀 4. Proof by Infinite Descent

The Story

Imagine someone tells you: “I have a magic staircase going down forever.”

You say: “Show me!” They walk down… and down… and down…

But wait—if you start at step 5, you can only go down 5 times! There’s no infinite staircase of positive integers!

This is Fermat’s method of Infinite Descent: If assuming something leads to an infinite decreasing sequence of positive integers, that assumption must be FALSE.

graph TD
    A["Start: n₁"] --> B["Smaller: n₂"]
    B --> C["Even smaller: n₃"]
    C --> D["n₄ < n₃ < n₂ < n₁"]
    D --> E["🚫 IMPOSSIBLE!<br>Can't go forever"]

Simple Example

Prove: √2 is irrational.

Assume the opposite: √2 = a/b where a and b are positive integers with no common factors.

The Descent:

1. √2 = a/b means 2b² = a²
2. So a² is even, which means a is even
3. Write a = 2c
4. Then 2b² = 4c², so b² = 2c²
5. So b is even too!
6. But wait—both a and b are even, contradicting “no common factors”
7. Actually, we can keep finding SMALLER pairs with the same property
8. This descent can’t go on forever → Contradiction!

🐦 5. Pigeonhole Principle

The Story

You have 10 pigeons and 9 pigeonholes. Every pigeon needs a hole.

What happens? At least one hole has 2 or more pigeons!

This simple idea is INCREDIBLY powerful.

The Rule

If n+1 objects go into n containers, at least one container has 2+ objects.

Generalized: If kn+1 objects go into n containers, at least one container has k+1 or more objects.

Simple Example 1

Problem: In any group of 13 people, at least 2 share a birthday month.

Proof:

• Pigeons = 13 people
• Holes = 12 months
• 13 > 12, so at least 2 people share a month! ✓

Simple Example 2

Problem: Pick any 5 integers. Prove that 2 of them have the same remainder when divided by 4.

Proof:

• Pigeons = 5 integers
• Holes = 4 possible remainders (0, 1, 2, 3)
• 5 > 4, so at least 2 integers share a remainder! ✓

A Magical Application

Problem: In any sequence of n²+1 distinct numbers, there exists either an increasing subsequence of n+1 numbers OR a decreasing subsequence of n+1 numbers.

This is the famous Erdős–Szekeres theorem, proven using pigeonhole!

🔮 6. Irrationality Proofs

The Big Idea

How do you prove a number CAN’T be written as a fraction? You use proof by contradiction!

Assume it CAN be written as p/q (in lowest terms), then find something impossible.

Classic Example: √2 is Irrational

The Setup: Assume √2 = p/q where gcd(p,q) = 1 (lowest terms).

The Magic Trick:

1. Square both sides: 2 = p²/q²
2. So p² = 2q²
3. This means p² is even
4. So p is even (if p were odd, p² would be odd)
5. Write p = 2k
6. Then 4k² = 2q², so 2k² = q²
7. So q² is even, meaning q is even
8. But BOTH p and q are even! This contradicts gcd(p,q) = 1

Conclusion: Our assumption was wrong. √2 is irrational! 🎉

Another Example: √3 is Irrational

Assume: √3 = p/q with gcd(p,q) = 1

The Proof:

1. 3 = p²/q², so p² = 3q²
2. p² is divisible by 3, so p is divisible by 3
3. Let p = 3k, then 9k² = 3q², so q² = 3k²
4. q² is divisible by 3, so q is divisible by 3
5. Both p and q divisible by 3 → Contradicts gcd(p,q) = 1!

Result: √3 is irrational! ✓

🎯 Summary: Which Tool When?

🌈 The Detective’s Wisdom

These six tools are like superpowers:

1. Well-Ordering → “The smallest one exists!”
2. Induction → “Knock down all dominoes!”
3. Strong Induction → “Use ALL your history!”
4. Infinite Descent → “Impossible infinite stairs!”
5. Pigeonhole → “Something must overlap!”
6. Irrationality → “Assume and explode!”

With these tools, you can prove things that seem impossible to check directly. You don’t need to verify infinity—you just need clever reasoning!

Now go forth, young detective, and prove some truths! 🔍✨