Euler's Eyes
2026-10-16
Examples do not prove: Euler, Pascal and induction
Calculate $n^2+n+41$ for $n=0,1,2,3,\ldots$
$$41,\ 43,\ 47,\ 53,\ 61,\ 71,\ 83,\ 97,\ 113,\ 131,\ \ldots$$They are all prime. Keep going up to $n=39$, and the result, $1601$, is still prime. Forty cases in a row, not one exception. In 1772, Leonhard Euler drew attention to this remarkable formula. And yet it does not produce only primes: with $n=40$,
$$40^2+40+41=1600+40+41=1681=41^2.$$Forty examples proved nothing. One counterexample brought everything down.
The temptation of cases
Euler’s polynomial is not an isolated curiosity. In 1640, Pierre de Fermat observed that the numbers $2^{2^n}+1$ gave
$$3,\quad 5,\quad 17,\quad 257,\quad 65\,537,$$all prime, and conjectured that every number of this form would be prime. In 1732, Euler showed that the next one, $2^{32}+1=4\,294\,967\,297$, equals $641\cdot6\,700\,417$. To this day no other prime of this form is known.
Students feel the same temptation. In a study published in 2000, the English researchers Lulu Healy and Celia Hoyles asked about 2,500 students aged 14 and 15 to assess several arguments for the claim “the sum of two even numbers is always even”. Many preferred the arguments that checked examples ($2+4=6$, $10+12=22$, …) because they understood them; at the same time, they thought the algebraic argument, with $2a+2b=2(a+b)$, was the one the teacher would mark highest. For them, the algebraic proof was a formality done for the teacher, and the examples were what actually convinced.
The ellipsis hides a rule
The most dangerous sign on this page is the most discreet one: the ellipsis, $\ldots$ When one writes
$$1+3+5+\cdots+(2n-1)=n^2,$$the three dots ask the reader to guess the rule from a few terms and extend it forever. It is an economical notation and, at the same time, a promise: “the pattern goes on”. But Euler’s polynomial shows that patterns can stop going on.
The formula above is easy to check in the first cases: $1=1^2$, $1+3=4=2^2$, $1+3+5=9=3^2$. A figure suggests why: each odd number is an L-shaped layer that turns one square into the next.
The figure is convincing, but it is still one figure, with five layers. How do you turn “and so on” into certainty?
Pascal’s two lemmas
The clearest answer came from Blaise Pascal, in the Treatise on the Arithmetical Triangle, written in 1654. When proving a property that held in every row of the triangle, he wrote:
Although this proposition contains an infinity of cases, I shall give a very short proof of it, assuming two lemmas. The first, which is self-evident, that this proportion is found in the second base. The second, that if this proportion is found in any base, it will necessarily be found in the following base.
— Blaise Pascal, Treatise on the Arithmetical Triangle, consequence 12
This is the principle of mathematical induction, with its two pieces. The base case: the claim holds in the first case. The step: if it holds in any case, it holds in the next one. With both pieces, the claim holds in every case, like a row of dominoes in which the first falls and each one knocks over the next.
Here is induction applied to the sum of odd numbers.
- Base case. For $n=1$: $1=1^2$. It holds.
- Step. Suppose that $1+3+\cdots+(2k-1)=k^2$ for some $k$. Adding the next odd number, $2k+1$, to both sides:
It holds for $k+1$. By the principle of induction, it holds for every $n$. $\blacksquare$
Notice what happened to the ellipsis. Before, it asked the reader to trust the pattern. After the induction, the pattern has been described by an explicit rule, “from $k$ to $k+1$, add $2k+1$”, and proved. The proof is the L-shaped layer of the figure, written in algebra: $k^2+(2k+1)=(k+1)^2$. Figure and induction say the same thing, but only the second holds for all the layers at once.
Exercise: Euler fails again
Show, without a calculator, that $n^2+n+41$ is not prime for $n=41$. Just take out the factor $41$: $41^2+41+41=41\cdot(41+1+1)=41\cdot43$. The form of the expression already gives the factor away. For $n=40$, the trick is different: $40^2+40+41=40\cdot41+41=41\cdot41$.
Exercise: Gauss's sum by induction
Prove that $1+2+\cdots+n=\frac{n(n+1)}2$ for every $n\geq1$.
Base case: for $n=1$, $1=\frac{1\cdot2}2$. Step: suppose that $1+2+\cdots+k=\frac{k(k+1)}2$. Adding $k+1$:
$$\frac{k(k+1)}2+(k+1)=\frac{k(k+1)+2(k+1)}2=\frac{(k+1)(k+2)}2,$$which is the formula with $k+1$ in place of $k$. By the principle of induction, it holds for every $n$. $\blacksquare$
Chapter index · ← The words of a proof: let, suppose, hence, ∎ · How to read a proof: a guide and a glossary →