Counterexamples to "Naive Induction"

Question

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.

Answer 1

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!

Answer 2

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

Answer 3

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.

Answer 4

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.