6
$\begingroup$

I was teaching a nine-year-old friend about prime numbers. When I asked him if he thought there were finitely or infinitely many primes, he answered confidently that there must be an infinite number. "How do you know?" I asked. "Because I can keep thinking up larger and larger primes. It's easy!" By way of proof, he came up with a new larger prime.

I call this "Naive Induction" (there might be a better term). I am looking for not-too-complicated counterexamples where

  1. It appears to be the case that there are infinitely many members of a set, or (equivalently) that some property is true for all integers, but

  2. It can be demonstrated that there is a largest member of the set, or a largest number with some property.

Any suggestions? Thanks.

$\endgroup$
4

4 Answers 4

7
$\begingroup$

This isn't what you're looking for, but it's semi - related.

Euler's polynomial $n^2 + n +41$ generates primes for integers $n = 0$ to 39. It seems when you start plugging in numbers and checking that this always gives a prime!

$\endgroup$
2
  • $\begingroup$ This fits the definition well, if we let $P(n)$ be the assertion that for all natural numbers $k\le n$, the number $k^2-k+41$ is prime. $\endgroup$ Sep 12, 2012 at 20:01
  • $\begingroup$ This is a good place to start, and very approachable. Thanks. $\endgroup$
    – David
    Sep 12, 2012 at 20:55
7
$\begingroup$

You may be interested in what Richard K. Guy has dubbed The Strong Law of Small Numbers. (The link above happens to be accessible. You could also look for the original American Mathematical Monthly papers, including The Second Strong Law of Small Numbers.

For primes, there are many interesting examples in Prime Number Races (Andrew Granville and Greg Martin). There are quite a few reasonable conjectures about the distribution of primes that first fail at very large numbers.

$\endgroup$
3
  • $\begingroup$ I loved reading Guy's article. Quite entertaining and simultaneously informative. $\endgroup$ Sep 12, 2012 at 20:33
  • $\begingroup$ Very deservedly, the articles I mentioned have won writing awards. $\endgroup$ Sep 12, 2012 at 20:41
  • $\begingroup$ Thanks, André. These look great. I downloaded the AMM paper you referenced, too. They're interesting in their own right, but it will take some time to filter out those examples that are approachable to Eli (whom I'm babysitting tonight). $\endgroup$
    – David
    Sep 12, 2012 at 20:59
7
$\begingroup$

I just came across an example that really remind me of this question. This comes from a kiddie colloquium talk given by T. Church at Stanford. I quote the abstract of the seminar.

Define a sequence of integers by $a_0 = 3$, $a_1 = 0$, $a_2 = 2$, and then recursively by $a_{n+3} = a_n + a_{n+1}$. Calculate out a few terms, or a few thousand, and you'll notice a curious pattern: the $n$-th term $a_n$ is divisible by $n$ exactly when $n$ is prime! The first counter-example is $n = 271441$, for which $a_n$ has over thirty thousand digits.

$\endgroup$
4
$\begingroup$

My first thought was Goodstein's theorem which seems "obviously false",

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .