Mathematics Educators Stack Exchange is a question and answer site for those involved in the field of teaching mathematics. It only takes a minute to sign up.
Sign up to join this community
Suppose that I want to show a student that empirical evidence in mathematics is not enough and we do need proofs, what kind of examples can I use?
By empirical evidence, I mean that (most of the time) you cannot simply check the statement $S(n)$ for $n \in \{1,\dots, 10^9\}$ and conclude it's true for all $n \in \mathbb N$.
There are some collections of such examples at sister sites:
Conjectures that have been disproved with extremely large counterexamples? at Mathematics Stack Exchange.
Examples of eventual counterexamples at MathOverflow.
One rather simple example that can be checked with a calculator is the conjecture by Fermat, that all numbers of the form $$2^{2^n}+1, \qquad n \in \mathbb N_0$$ are prime.
In fact,
So the original conjecture is clearly false, but it took nearly 100 years to find the counterexample. All following Fermat numbers appear to be composite, but this is an open problem.
Strangely, just this morning I asked Wolfram|Alpha to compute the sum $$\sum_{n=1}^{\infty}{\frac{1}{n\sin(n)}}$$ and it returned the approximate value of $-0.863507$. I asked it to "show more digits", and it returned a new approximation:
$-94.377284731050845020943145217217734512865979242824685504875914407196948018$
I was trying to illustrate a series for which convergence (or divergence) is difficult to determine and was treated to some very different approximations. Note that Wolfram did not tell whether the series converges.
There's a great paper out there called "The Strong Law of Small Numbers", by Richard K Guy, which provides numerous examples of misleading patterns. A PDF copy can be found here: https://www.ime.usp.br/~rbrito/docs/2322249.pdf
The YouTube channel "Numberphile" (if you aren't already a subscriber, which you should be) has a video by the same name that's also worth a look. It's where I first learned about the paper.
On a personal note, I remember stumbling across Guy's Example 8 myself in a different form (very simply: construct a list starting with 0, ending with 1, and containing all unique fractions between the two where the denominator is $\leq n$. Now count the members of the list. You'll find that $n=1$ produces $2$, $n=2\rightarrow3$, $n=3\rightarrow5$, $n=4\rightarrow7...$) The sense of being on to something weird and exciting and possibly new, then suddenly seeing it all fall apart was something I'll never forget. Finding out it had been written up in a paper twenty-plus years ago was the cherry on the sundae, for sure.
There is an old joke describing how various scientific disciplines "prove" that all odd numbers are prime. The part for mathematicians goes
1 is a special case, 3 is prime, 5 is prime, 7 is prime, the proof by induction is left to the reader.
The Miller-Rabin test may be a good example. It identifies "industrial strength primes," numbers which are strongly indicated to be prime through testing, but have not actually been proven to be prime. It is based off of the proof that $a^d \equiv 1 (mod\;p)$ for all prime numbers. The test flips that around into its contrapositive, and explores the idea that if we look for an $a$ which does not satisfy that equation, then we have found a "witness" which shows that $p$ is not prime. It can be shown that all composite numbers have at least one witness, but a simple algorithm for determining it has never been found. Instead, we test many $a$ and, if we find no witnesses, then we say $p$ is an "industrual strength prime" because we took a good swing at it and failed to disprove its primality.
As it turns out, testing small values of a is enormously successful. So successful that you might make the assumption that testing just $a=2$ and $a=3$ is sufficient to prove a number is prime. And you'd be right, so long as the number is smaller than 1,373,653, which is the first point where that test suggests a composite number is prime.
Maple's isprime() function relies on this test. It tests $a=2$, $a=3$, $a=5$, $a=7$, and $a=11$. This turns out to be a very fast and enormously effective test. But there are numbers which fail this. In fact, one mathematician identified a particular 397-bit number which passes all tests from $a=2$ through $a=307$, and yet is composite.
There is a classic undergrad example (apparently going back to Euler) still missing in this list:
$$n^2+n+41 \text{ is prime}$$
which is true for all $n<40$ but fails at $n=40$.
The Yule-Simpson paradox or effect. It is an important result in statistics that says you cannot simply plug numbers into a statistical engine and pop out a meaningful answer.
In this example, from Wikipedia, the regression line is the dashed line. It looks like there is a decreasing effect. The true effect is that there is some categorical variable and in both possible states, the effect is an increasing one.
The famous example, which is in the Wiki article, is the UC Berkley case where there was apparent and substantial discrimination against women for admission. What was found was that there was a small, but statistically significant bias for women over men once the academic department was controlled for.
It requires a person to think about subpopulations as well as the total population. The danger is that simple analysis of the data is very misleading. The mathematical intuition should be that if every subpopulation is increasing, the population should be increasing, but that is not true.
Think of that from a policy or voting perspective. If society is worse off for each increase in $x$, then society should suppress $x$. However, if every subpopulation is improved by $x$ increasing, then $x$ should be amplified. In the graphic above, the actual intuition should not be about suppressing $x$ but about shifting the subpopulation represented by the red line to the left. It would be even better to shift all subpopulations to the left, while amplifying $x$ at the same time. It is the intercept that is the secret story in this diagram.
Here is a straightforward example that knowing the first $k$ terms (no matter how big $k$ is) of a sequence $(x_n)$ tells you very little about the term $x_{k+1}$: I can generate a sequence whose first $k$ terms are $1,2,\dots,k$ but whose $(k+1)^{{\rm st}}$ term is an arbitrary $m$ of my choosing. For the given $k$, let $x_n = n + \frac {m-n}{k!}(n-1)(n-2)\dots(n-k)$.
Now, for any $n$ up to $k$, a factor in the product is $0$, forcing the entire product to be $0$, leaving $x_n=n$. Meanwhile, at $n=k+1$, the product $(k+1-1)\dots(k+1-k)=k!$, and straightforward arithmetic shows $x_{k+1}=m$.
Much more in fact is true. Linear algebra can be used to show, given completely arbitrary first terms $a_1,\dots,a_{k+1}\in\mathbb R$, there is a sequence $(x_n)$ for which $x_1=a_1,\dots,x_{k+1}=a_{k+1}$, and the generic term $x_n$ of $(x_n)$ is given as a polynomial in $n$ with degree at most $k$. (Indeed, the terms don't even need to be the ``first'' terms, we just need to know which terms they are.)
Without knowing something more about a sequence of real numbers than just ``these are some of the terms'', nothing of substance can be concluded about the sequence.
Edit (30 May 2019): Many standardized tests have questions along the lines of ``If a sequence starts with the numbers $1$, $2$, $4$, $8$, what is the next term in the sequence?" then proceeds to have a multiple choice answer, providing four numbers/answers. One main point behind this example is that all four answers are correct.
The Pell equation $x^2-Dy^2=1$ (where $x$ and $y$ are positive integers) admits solutions if the natural number $D$ is not a square number. But for $D=61$ the smallest solution is astonishingly great: you can derive an example from this fact. https://proofwiki.org/wiki/Pell%27s_Equation/Examples/61
If you are open to other fields that strongly rely on mathematics, you can use the Rayleigh-Jeans catastrophe as an example:
The term "ultraviolet catastrophe" was first used in 1911 by Paul Ehrenfest, but the concept originated with the 1900 statistical derivation of the Rayleigh–Jeans law. The phrase refers to the fact that the Rayleigh–Jeans law accurately predicts experimental results at radiative frequencies below 105 GHz, but begins to diverge with empirical observations as these frequencies reach the ultraviolet region of the electromagnetic spectrum.1 Since the first appearance of the term, it has also been used for other predictions of a similar nature, as in quantum electrodynamics and such cases as ultraviolet divergence.
The beginning times of quantum physics is full of such examples. This particular one was solved by Max Planck and physics has never been the same since then.
Try representability by the sum of three cubes, $$ x^3 + y^3 + z^3 = k \text{.} $$
Early computer search paper, that turned up no new representable $k$s.: Gardiner, V.L., R.B. Lazarus, and P.R. Stein, Solutions of the Diophantine Equation $x^3 + y^3 = z^3 - d$, 1964. In this paper, no representations are found for $d = k = 30$ and $d = k = 33$ (and several more $d = k < 1000$). Contains the lines "Nevertheless, it is in our opinion rather unlikely that all the missing $|d|$'s will turn out to be expressible as sums of three cubes. It would be of interest to attempt a proof that, say, 30 cannot be so represented."
Recent paper: Huisman, S., Newer sums of three cubes, 2016. This paper finds that $33$ is the least $k$ with no known representation, so a representation for $k = 30$ was found in the interim.
Recent video: Haran, B. and A. Booker, 42 is the new 33 - Numberphile, 12 March 2019. A much larger empirical search found a representation for $k = 33$, leaving $k = 42$ as the least $k$ without a known representation.
Moral: empirical searches keep being inadequate.
XKCD compiled a list of approximations several years back:
Many are just funny trivia, but you could use most of them as examples of the limits of empirical evidence, because empirical estimations using these formulas would seem to be strong evidence that they are correct, when mathematically they are complete nonsense.
If you keep a running tally of primes of the form $4k+1$ vs $4k+3$, it seems like the latter are always at least as numerous. But it was eventually shown each type takes the lead infinitely many times; it's just you have to get into huge numbers before the first lead for $4k+1$.
