# 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](https://en.wikipedia.org/wiki/Mersenne_prime).) 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](https://en.wikipedia.org/wiki/P%C3%B3lya_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](https://johncarlosbaez.wordpress.com/2018/09/20/patterns-that-eventually-fail/) 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://mathoverflow.net/questions/15444/examples-of-eventual-counterexamples)
[https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Guy697-712.pdf](https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Guy697-712.pdf)