# Engineer's Induction

# 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 Factorization | Number of Prime Factors of $n$ | 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 $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