# 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$).

• If you're willing to accept an n>2 condition, then Fermat's Last Theorem. The case for n doesn't afford you any insight for the case n+1. Though at that level of learning, they'd probably just have to accept that that's the case. – Neil W May 23 '15 at 6:58
• @NeilW That's a great example, highly nontrivial. :) Maybe not super instructive, but still a good example. – user223391 May 23 '15 at 7:00
• All sorts of statements similar to ‘for all natural numbers $n$, $n^3-n$ is divisible by $6$. Proof by induction isn’t hard, but it’s certainly unnecessarily complicated. – Brian M. Scott May 24 '15 at 7:18
• For any natural number $n$, there is a prime number larger than $n$. – mjqxxxx May 25 '15 at 22:59
• Why do you consider this important? What I mean is, if you actually found students in your class trying to use induction in a setting where they shouldn't then you would have a real example from your teaching to provide in future courses. And if you don't really find students attempting induction in a setting where it doesn't seem viable then the whole thing is a non-issue. Induction is a very useful idea, so why try to discourage it so soon after introducing it? I can think of lots of examples in number theory that don't proceed by induction on $n$, but the statements will sound [contd.] – KCd May 26 '15 at 0:14

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.

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.

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...

• Or another way of proving this is another example I had in mind. For all $n\in \mathbb{N}$, $n<n+1$. If you know that $0<1$, you can just add $n$ to both sides. This is equivalent to your statement. – user223391 May 23 '15 at 6:33
• I don't know, this seems just as easy by induction: it's true for $n=0$, and $n/(n+1)<1 \implies n<n+1 \implies n+1<n+2 \implies (n+1)/(n+2)<1$. – mjqxxxx May 25 '15 at 22:54

There's the classic example that $$1 + 2 + \ldots + n = \dfrac{n(n+1)}{2},$$

which can be proved without induction using Gauss's trick, or the geometric argument involving a rectangular grid.

In a similar vein, showing

$${n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k} \quad \text{for } 1 \le k \le n - 1$$

has a really straightforward combinatorial proof via path counting, while the algebraic or inductive reasoning is unnecessarily messy.

Induction works perfectly well for these, but it's not very easy or enlightening, given the alternatives.

• Why would you consider induction not easy for that summation identity? It is the example used to illustrate induction in any textbook I have read that discusses induction. – KCd May 25 '15 at 23:56
• @KCd That's a fair point. I suppose what I meant is that the induction-free alternative is computationally easier, and more illuminating, regardless. – pjs36 May 26 '15 at 0:03
• Yes, but I don't see how this will convince students that there are some results about positive integers for which induction is not a viable option (as far as we can tell, of course) since it is quite accessible to a beginner's level of understanding. – KCd May 26 '15 at 0:07
• @KCd It's easy to do by induction. There's just other ways of doing it as well. – user223391 May 26 '15 at 0:27

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.

Theorem: For all $n\in \mathbb{N}$, $$n^2 + 1 \geq 2n.$$

Easy to prove by just observing that $(x-1)^2 \geq 0$ for all $x\in \mathbb{R}$.

Not only is this way quicker than writing out a proof by induction, but it works for all real numbers, not just natural numbers. So you have an easier proof of a stronger result!

For all n, there is no m such that m < n < m+1.