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 2p−1, where p 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 p:

p2p−1
p=22p−1=3
p=323−1=7
p=525−1=31
p=727−1=127

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 2p−1 are prime. However, let's check the next prime, p=11: 211−1=2047=23×89 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 p=11, 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 4=22 is considered to have 2 prime factors.) Checking the first few primes, we see that the conjecture holds:

n and Its Prime FactorizationNumber of Prime Factors of nOdd # of Prime Factors - Even # of Prime Factors
2 = 211
3 = 312
4 = 2 * 221
5 = 512
6 = 2 * 321
7 = 712

It turns out that the smallest counterexample is at the astounding value of n=906,150,257.

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 x and y. Consider the value of gcd⁡(x17+9, (x+1)17+9) for all positive integers x. It turns out that this function is equal to 1 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 8.42⋅1051. Pretty big number, right! Checking even the first few billion values of x 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 sinc(x)=sin⁡(x)/x. The following integrals all equal π/2:

∫0∞sin⁡(x)x dx=π2 ∫_0∞sin⁡(x)xsin⁡(x/3)x/3 dx=π2 ∫_0∞sin⁡(x)xsin⁡(x/3)x/3sin⁡(x/5)x/5 dx=π2 ∫_0∞sin⁡(x)xsin⁡(x/3)x/3sin⁡(x/5)x/5sin⁡(x/7)x/7 dx=π2

It turns out that the pattern holds until

∫_0∞sin⁡(x)xsin⁡(x/3)x/3sin⁡(x/5)x/5sin⁡(x/7)x/7⋯sin⁡(x/15)x/15 dx≈π2−2.31×10−11

This is because the sum of the coefficents 13+15+⋯+115>1. 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:

← All posts · View as Markdown