# Counterexamples to “Naive Induction”

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.

-
This could be a place to look. Some of them can be stated in a not-too-complicated way, I think. – Karolis Juodelė Sep 12 '12 at 19:57
possible duplicate of Examples of apparent patterns that eventually fail – tomasz Sep 12 '12 at 20:01
possible duplicate math.stackexchange.com/questions/194613/… – clark Sep 12 '12 at 20:31
Thanks for the pointers, I missed those in my search. I now have enough material to keep me busy for awhile. – David Sep 12 '12 at 21:00

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!

-
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. – André Nicolas Sep 12 '12 at 20:01
This is a good place to start, and very approachable. Thanks. – David Sep 12 '12 at 20:55

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.

-
I loved reading Guy's article. Quite entertaining and simultaneously informative. – Cameron Buie Sep 12 '12 at 20:33
Very deservedly, the articles I mentioned have won writing awards. – André Nicolas Sep 12 '12 at 20:41
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). – David Sep 12 '12 at 20:59

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

-

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.

-