What are statements about the natural numbers where induction is impossible or unnecessary to prove?

I'm looking for statements like "for all natural numbers, ____" where induction would be impossible or unnecessarily complicated. This is for pedagogical reasons. When students first learn induction, they want to prove every statement about natural numbers by induction, even when it is entirely not necessary or possible. It would be nice to have examples to break "natural numbers implies induction".

For example: for all $n\in \mathbb{N}$, $\int_0^{2\pi} \cos(nx) dx=0$. If one tries to show this by induction, it would be way more complicated than necessary. You can just compute the integral directly (assuming you know $\sin(2n\pi)=0$).

Solution 1:

1) For all relatively prime positive integers $a$ and $m$ there is a prime number in the arithmetic progression $a$, $a+m$, $a+2m$, $a+3m,\dots$

Of course the general theorem is that there are infinitely many primes in each such progression, but the way I stated it by quantifying over all $a$ and $m$ is equivalent to the general version; for beginners I think the existence of a single prime in such a progression as $a$ and $m$ vary is easier to comprehend. In fact, because this special case implies the general case it is pretty inconceivable to me how this could be proved by induction. The special case $a = 1$ can be proved in a simpler way, using the $m$-th cyclotomic polynomial, so you have a theorem with a single parameter in it, and I've never seen a proof of that version by induction either.

2) For $n \geq 2$, the partial sums $H_n = 1 + 1/2 + 1/3 + \cdots + 1/n$ are not integers.

The proofs I know are based on studying the highest power of $2$ less than or equal to $n$ rather than any kind of direct induction on $n$. If $H_n$ is not an integer how can that raw fact help you show $H_{n+1}$ is not an integer? To use induction you'd be trying to show a "non-property" persists from $n$ to $n+1$ (or from all integers from $2$ to $n$ on to $n+1$). If someone says that the proof is by induction on the highest power of $2$ less than or equal to $n$ then I'd point out that the proof does not use anything about $n$ to get the result for $n+1$.

3) A partial example: for $n \geq 2$, the number $\sqrt[n]{2}$ is irrational.

I consider this partial because, while the direct statement is not easily accessible to induction (the numbers $\sqrt[n]{2}$ and $\sqrt[n+1]{2}$ are linearly disjoint over $\mathbf Q$, so it's hard to imagine how, to a beginner, the irrationality of $\sqrt[n]{2}$ could help you prove irrationality of $\sqrt[n+1]{2}$), it could be seen as a consequence of the more general result that if a prime -- or just the specific prime $2$ -- divides a product of $n$ integers then it must divide one of them, and that is provable by induction.

4) Consider giving the class some unsolved problems about integers, e.g., for every $n \geq 2$ the infinite series $1 + 1/2^n + 1/3^n + 1/4^n + \dots$ is irrational. It's proved for even $n$ and for $n = 3$, but unproved for $n = 5$.

5) Bertrand's postulate: for every integer $n \geq 1$ there is a prime number $p$ with $n \leq p \leq 2n$. (I use $\leq$ instead of $<$ so the result is true all the way down to $n = 1$.)

More generally, lots of theorems about the location of prime numbers are not accessible to proofs by induction (so far) since primality is not really a condition that respects the passage from $n$ to $n+1$.

6) Lagrange's four-square theorem: every integer $n \geq 1$ is a sum of four perfect squares.

That is proved by doing it first for primes (using special methods exploiting primality of $n$) and then concluding it in general by prime factorization and Euler's four-square identity. You could say this is proved by induction on the number of prime factors of $n$, but to a beginner it's definitely defensible to say this can't be proved as far as we can tell by reasoning from $n$ to $n+1$. Nobody knows how to turn a representation of $n$ as a sum of four squares into a representation of $n+1$ as a sum of four squares.

Solution 2:

There is a whole family of examples similar to the proposition that $n^3-n$ is divisible by $6$ for each natural number $n$. Proof by induction isn’t hard, but it’s certainly unnecessarily complicated.

Solution 3:

For all $n \in \mathbb{N}$, $\frac{n}{n+1} < 1$.

The slick algebraic proof of this would be $\frac{n}{n+1} = 1 - \frac{1}{n+1} < 1$ since $\frac{1}{n+1}>0$ for all $n \in \mathbb{N}$. Induction would be much messier...

Solution 4:

Start with the list of all $2^n$ vectors of length $n$ of $+1$s and $-1$s. Someone changes some of the entries to $0$. Show that there is always a non-empty collection of rows which sums to the zero vector.

This looks like the perfect case for induction (on $n$), but the two proofs I'm aware of don't use induction; induction just doesn't seem to help here.