Examples of patterns that eventually fail

Question

Often, when I try to describe mathematics to the layman, I find myself struggling to convince them of the importance and consequence of "proof". I receive responses like: "surely if Collatz is true up to $20×2^{58}$, then it must always be true?"; and "the sequence of number of edges on a complete graph starts $0,1,3,6,10$, so the next term must be 15 etc."

Granted, this second statement is less logically unsound than the first since it's not difficult to see the reason why the sequence must continue as such; nevertheless, the statement was made on a premise that boils down to "interesting patterns must always continue".

I try to counter this logic by creating a ridiculous argument like "the numbers $1,2,3,4,5$ are less than $100$, so surely all numbers are", but this usually fails to be convincing.

So, are there any examples of non-trivial patterns that appear to be true for a large number of small cases, but then fail for some larger case? A good answer to this question should:

1. be one which could be explained to the layman without having to subject them to a 24 lecture course of background material, and
2. have as a minimal counterexample a case which cannot (feasibly) be checked without the use of a computer.

I believe conditions 1. and 2. make my question specific enough to have in some sense a "right" (or at least a "not wrong") answer; but I'd be happy to clarify if this is not the case. I suppose I'm expecting an answer to come from number theory, but can see that areas like graph theory, combinatorics more generally and set theory could potentially offer suitable answers.

Answer 1

The Sierpiński numbers would be a good example. All odd integers up to 10,221 have been checked and are known to lead to a prime number of the form $k2^n+1$, where $k$ is the original odd integer, and $n$ is any integer. One would think that, if the trend continued, there would be no such integers. However, several integers have been proven to generate only composite numbers of the form $k2^n+1$. The smallest such integer known is $78,\!557$. In addition, it has been proven that there are infinitely many such integers.

Answer 2

Let $n>0$ and $s_n=\sum_{k=1}^n k$. Now look at the expression $\displaystyle\frac{s_n!}{(s_n-n)!}$. You'll get
$$\frac{1!}{0!}=1=1!,\frac{3!}{(3-2)!}=6=3!,\frac{6!}{(6-3)!}=120=5!,\frac{10!}{(10-4)!}=5040=7! $$ but pattern $\displaystyle \frac{s_n!}{(s_n-n)!}= (2n+1)!$ stops here since $\frac{15!}{(15-5)!}= 360360\neq 9!=362880$

Answer 3

It seems the Mertens conjecture (see link) hasn't been mentioned yet. Conjectured in the 19th century and disproved about hundred years later, the amazing fact is that there was "overwhelming numerical evidence" that it is true - but it wasn't. In fact, there is no known counterexample so far.

Answer 4

Is there a pair of amicable numbers with distinct smallest prime factors? For quite a long time no example of such a pair was known. The first such pair was discovered through computer search in October 2015 (but only noticed by humans three months later):$$445\,953\,248\,528\,881\,275=3^2\times5^2\times7\times13\times19\times37\times43\times73\times439\times22\,483$$and$$659\,008\,669\,204\,392\,325=5^2\times7\times13\times19\times37\times73\times571\times1\,693\times5\,839.$$

Answer 5

Another example, hopefully not too technical for a layman, is the story of Skewes' number (see link) where there was, again, a lot of numerical evidence that $\pi(x)$ was always less than $\operatorname{li}(x)$ - until Littlewood proved that this was not the case and Skewes was the first one to establish bounds for the smallest counterexample.

Answer 6

Given that nobody has mentioned it yet, Euler conjectured that Mutually Orthogonal Latin Squares (MOLS) of order $n$ do not exist for all $n = 4k+2$, based on the observation they do not exist for $n=2$ and the fact that he could not find one of order 6. Fairly straightforward constructions existed for non $4k+2$ orders. Gaston Tarry in 1901 proved by exhaustion that none exists of order 6, and Euler's conjecture stood until the 1950s when counterexamples of order 10 and 22 were found. It was finally proven that they do exist for all $n = 4k + 2 \geq 10$ in 1959, against the intuition of one of the greatest mathematicians of all time.

Answer 7

An interesting case is as follows (though no counterexample is known as yet):

Let $p_n$ be the n$^{th}$ prime. Consider n$^{th}$ prime raised to $1/n$$^{th}$ power, i.e. $p_n^{\frac{1}{n}}$. Firoozbakht conjectured that $p_n^{\frac{1}{n}}$ is a strictly decreasing function. But, mathematicians believe it to be false. This may become one the best examples of such patterns if and when it is proven to be false.

Answer 8

I understand this observation may be child's play for most people here, but i believe it would be interesting for people with little background. To be precise, i just want to leave an observation concerning the idea that "interesting patterns must always continue", mainly because i think it is simple and didactic:

It is a direct consequence of the construction of Lagrange polynomials that, given $a_1, \dots a_n \in \mathbb{R}$ (that can be understood as the "first $n$ terms of a "pattern"), for each $a \in \mathbb{R}$ there exists a polynomial $f$ such that $f\left ( i \right ) = a_i$ and $f\left ( n+1 \right ) = a$. This gives an easy way to show the falsehood of the idea that "interesting patterns must always continue". For example, one could take the numbers 1, 2, 4, 8, 16, 32 and then 65 instead of 64, and with the consequence mentioned give a polynomial such that gives a pattern, but not the one expected. If you want a pattern true for a large number of small cases, but eventually false, the same example can be taken.

A broader result would be: Let $K$ be a field of characteristic zero, $a_1, \dots a_n \in K$.Then, for each $a \in K$ there exists $f \in K\left [ x \right ]$ such that $f\left ( i \right )=a_i$ and $f\left ( n+1 \right )=a$.

Answer 9

\begin{array}{|c|c|} \hline \text{Number}& \text{Is prime} \\ \hline 91 & \color{red}{\text{False}} \\ \hline 9901 & \color{blue}{\text{True}} \\ \hline 999001 & \color{red}{\text{False}} \\ \hline 99990001 & \color{blue}{\text{True}} \\ \hline 9999900001 & \color{red}{\text{False}} \\ \hline 999999000001 & \color{blue}{\text{True}} \\ \hline 99999990000001 & \color{red}{\text{False}} \\ \hline 9999999900000001 & \color{blue}{\text{True}} \\ \hline 999999999000000001 & \color{red}{\text{False}} \\ \hline \end{array}

Can you guess if $99999999990000000001$, the next in the sequence, is a prime number? As it turns out, it is not! And it seems that all the next terms are not prime too.

Answer 10

The partition numbers https://oeis.org/A000041 2,3,5,7,11, and then 15 instead of 13.

Answer 11

The smallest integer $n>719$ such that $\binom{n}{13}+\binom{n+1}{13}$ has exactly $13$ prime factors (counted with multiplicity) is $84138143707644$.

This is a counterexample to the statement that $\binom{n}{13}+\binom{n+1}{13}$ has at least $14$ prime factors (counted with multiplicity) for all integers $n\gt797$.

Answer 12

If one who has a 10 digit calculator, sees the value of $e$ as $$ 2.7\color{red}{18281828}$$ but if one checks in a more powerful computer or in OEIS then $$ e = 2.7\color{red}{18281828}45904...$$

Clearly the pattern fails.

Answer 13

The below two patters fail early on and nobody who's spent some time on basic maths would think they would continue. But considering they're so easily stated, I feel they're still in the spirit of the question for a truly lay audience.

---

The smallest integer greater than one that can be written entirely in ones and zeros in base $2$ is $2$: $$2=(1)\cdot 2^1+(0)2^0$$

The smallest integer greater than one that can be written entirely in ones and zeros in bases $2$ and $3$ is $3$: $$3=(1)3^1 + (0)3^0=(1)2^1+(1)2^0$$

The smallest integer greater than one that can be written entirely in ones and zeros in bases $2$,$3$, and $4$ is $4$: $$4=(1)4^1+(0)4^0=(1)3^1+(1)3^0=(1)2^2+(0)2^1+(0)2^0$$

The smallest integer greater than one that can be written entirely in ones and zeros in bases $2$,$3$,$4$, and $5$ is $82000$. First seen in this video.

---

Often seen in erroneous proofs of the infinity of primes (this question has been viewed 20k times,e.g.), one can't reliably construct a prime just by adding 1 to the product of all previous primes.

$2+1=3$, prime

$2\cdot3+1=5$, prime

$2\cdot3 \cdot 5+1=31$, prime

$2\cdot3 \cdot 5 \cdot 7+1=211$, prime

$2\cdot3 \cdot 5 \cdot 7 \cdot 11+1=2311$, prime

$2\cdot3 \cdot 5 \cdot 7 \cdot 11 \cdot 13+1=30031$, composite