Engineer’s Induction

April 28th, 2022 · 5:34 AM EDT · 566 words

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 $2^p - 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$:

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 $2^p - 1$ are prime. However, let’s check the next prime, $p = 11$: $$2^{11} - 1 = 2047 = 23 \times 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 = 2^2$ is considered to have 2 prime factors.) Checking the first few primes, we see that the conjecture holds:

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(x^{17} + 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 \cdot 10^{51}$. 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 $\text{sinc}(x) = \sin(x)/x$. The following integrals all equal $\pi/2$:

$$\int_0^{\infty} \frac{\sin(x)}{x}\ \text{d}x = \frac{\pi}{2}$$ $$\int_0^{\infty} \frac{\sin(x)}{x} \frac{\sin(x/3)}{x/3}\ \text{d}x = \frac{\pi}{2}$$ $$\int_0^{\infty} \frac{\sin(x)}{x} \frac{\sin(x/3)}{x/3} \frac{\sin(x/5)}{x/5}\ \text{d}x = \frac{\pi}{2}$$ $$\int_0^{\infty} \frac{\sin(x)}{x} \frac{\sin(x/3)}{x/3} \frac{\sin(x/5)}{x/5} \frac{\sin(x/7)}{x/7}\ \text{d}x = \frac{\pi}{2}$$

It turns out that the pattern holds until

$$\int_0^{\infty} \frac{\sin(x)}{x} \frac{\sin(x/3)}{x/3} \frac{\sin(x/5)}{x/5} \frac{\sin(x/7)}{x/7} \cdots \frac{\sin(x/15)}{x/15}\ \text{d}x \approx \frac{\pi}{2} - 2.31 \times 10^{-11}$$

This is because the sum of the coefficents $\frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{15} > 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: https://mathoverflow.net/questions/15444/examples-of-eventual-counterexamples https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Guy697-712.pdf