Course contentsShow
← Mathematics
Lesson 2520 of 3,12150. Discrete Math — Logic and ProofFree lesson

Choosing the Right Proof Technique

Learn when to use ordinary induction, strong induction, or well-ordering based on problem structure.

Choosing the Right Proof Technique

You'll learn how to select ordinary induction, strong induction, or well-ordering based on the structure of the problem you're trying to prove.

Now that you've mastered three powerful proof techniques for statements about natural numbers, the key question becomes: which one should you use? While these methods are logically equivalent, choosing the right tool makes your proof cleaner and more natural.

Recognizing Problem Structure

Use Ordinary Induction when:

  • The statement at step n depends only on step n-1
  • You can build the next case directly from the previous one
  • Example: proving sum formulas like 1 + 2 + ... + n = n(n+1)/2
  • Analogy: Climbing a ladder one rung at a time—you only need the rung directly below you

Use Strong Induction when:

  • The statement at step n might depend on multiple earlier cases
  • Recursive definitions involve looking back more than one step
  • Example: proving properties of the Fibonacci sequence F(n) = F(n-1) + F(n-2)
  • Analogy: Building a brick wall where each brick might rest on several bricks below, not just the one directly beneath

Use Well-Ordering when:

  • You need to find a minimal counterexample
  • The proof involves "smallest" or "least" elements
  • Contradiction arguments feel most natural
  • Example: proving every integer > 1 has a prime factorization
  • Analogy: Finding the weakest link in a chain—if something fails, there must be a first failure point

Strategic Hints

If you're stuck, try strong induction—it's the most flexible since assuming more gives you more to work with. If the problem mentions "smallest" or "least," consider well-ordering.

Key Takeaway: Choose ordinary induction for sequential dependencies, strong induction for multi-step dependencies or recursive structures, and well-ordering when minimality or finding a smallest element drives the argument.