Engineer's Induction
What is Engineer's induction? Engineer's induction is when you deduce a pattern based on a small number of cases. For example, consider numbers of the form , where is a prime integer. (A prime number is a number that is only divisible by 1 and itself.) Let's look at the first few primes :
All of these numbers are prime. (These numbers are known as Mersenne primes.) By engineer's induction, we would think that all numbers of the form are prime. However, let's check the next prime, : So, we can see that the pattern no longer holds; the next number is not prime.
When doing math, engineer's induction is tempting, but I am going to show a multitude of examples where it doesn't hold. In our example, the first case where the pattern didn't hold was at , but I'll show plenty of examples where the first counterexample is much higher.
One infamous example is the Polya conjecture, which states that over 50% of positive integers less than a given number have an odd number of prime factors. (Repeated prime factors are counted each time that they appear, so that is considered to have 2 prime factors.) Checking the first few primes, we see that the conjecture holds:
| and Its Prime Factorization | Number of Prime Factors of | Odd # of Prime Factors - Even # of Prime Factors |
|---|---|---|
| 2 = 2 | 1 | 1 |
| 3 = 3 | 1 | 2 |
| 4 = 2 * 2 | 2 | 1 |
| 5 = 5 | 1 | 2 |
| 6 = 2 * 3 | 2 | 1 |
| 7 = 7 | 1 | 2 |
It turns out that the smallest counterexample is at the astounding value of .
Here's another example: let the function gcd(x, y), where x and y are integers, be defined as the largest integer that divides both and .
Consider the value of for all positive integers .
It turns out that this function is equal to for all x ... until x = 8,424,432,925,592,889,329,288,197,322,308,900,672,459,420,460,792,433. which is approximately . Pretty big number, right! Checking even the first few billion values of would never be able to get you this value.
I'll finish this blog with a classic example of why you can never assume anything from engineer's induction. The sinc function is defined as . The following integrals all equal :
It turns out that the pattern holds until
This is because the sum of the coefficents . Here is a great explanation for why this occurs. (Using this pattern, you can construct arbitrarily large counterexamples.)
I hope that I was able to convince you that "simply" checking a few small examples, or even a lot of small examples, is not sufficient to conclude that something must be true and go about to prove it. Engineer's induction is a quick-and-dirty tool for most problems, but there's a reason why the world of mathematics demands the rigor of a proof.
Additional reading: