# 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$:

$p$$2^p - 1 p = 2$$2^p - 1 = 3$
$p = 3$$2^3 - 1 = 7 p = 5$$2^5 - 1 = 31$
$p = 7$$2^7 - 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 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: 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(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.