What are some good low-prerequisite examples for the heuristic advice "If you cannot prove it, prove something stronger."?

Question

One useful trick in mathematics is to prove something stronger instead of the question asked.

This works well in induction proofs (because strengthening the claim also strengthens the induction basis):

Example: Prove $\frac1{1\cdot 2} + \frac1{2\cdot 3} + \dots +\frac1{(n-1)\cdot n} < 1$. This admits a simple induction proof if one proves the exact formula instead.

But there are also other examples

Example: Proving that inscribed angles in a circle are equal becomes easier when we try to show that all of them are half the central angle.

Of course, there are also lots of research examples that involve the trivialization of results as soon as new parameters are introduced or the whole problem is generalized to the "right" setting.

Now, my question is the following:

What are some good examples for the principle "Prove something stronger instead of the original statement" that would work well with first-year university students?

Some calculus is ok, as long as it is introductory content. But generally, the more basic, the better, because the point is to illustrate the principle.

Answer 1

For a very basic example, how about proving that 59549121058965346178 can be expressed as a product of primes? It is much easier to prove the stronger result that every positive integer can be expressed as a product of primes.

As a clarification, among professional mathematicians, the phrase "a product of primes" includes the case "a product of no primes" (which is one) or "a product of one prime" (which is the prime itself) as well as "a product of two or more primes".

Answer 2

I think it is easier to prove Cauchy-Schwarz in an arbitrary inner product space than for dot product on $\mathbb{R}^n$, because trying to prove it in general limits the selection of tools you have available: you only have inner product space axioms. In $\mathbb{R}^n$, you might try all kinds of explicit horrible calculations to try to get at the inequality. This illustrates in general why proving a stronger statement is oftentimes easier: by working towards a stronger result you limit the search space of possible proofs.

Answer 3

Consider the definite integral $$\int_{0}^{1}\frac{x^{10} - 1}{\ln x} dx$$ This can be evaluated fairly easily by considering instead the more general integral $$\int_{0}^{1}\frac{x^{b} - 1}{\ln x} dx,$$ where $b \geq 0$ is an arbitrary parameter, and using a method called "differentiating the integral" or "differentiating under the integral sign".

Let $F(b) = \int_{0}^{1} \frac{x^{b} - 1}{\ln x} dx.$ Ignoring the matter of interchanging the order of integration with differentiation (this is justified in older advanced calculus texts), we have

$$F'(b) \;\; = \;\; \frac{d}{db} \int_{0}^{1}\frac{x^{b} - 1}{\ln x} dx \;\; = \;\; \int_{0}^{1}\frac{d}{db} \left( \frac{x^{b} - 1}{\ln x} \right) dx \;\; = \;\; \int_{0}^{1} x^{b} dx \;\; = \;\; \frac{1}{b+1}$$ Integrating both sides of $F'(b) = \frac{1}{b+1}$ with respect to $b$ gives $F(b) = \ln (b+1) + C$ for some constant $C.$ We can find $C$ by using a value of $b$ for which we know the value of $F.$ Clearly, $F(0) = 0.$ This implies that $C = 0,$ and so $F(b) = \ln(b+1).$ Hence, the first integral I gave has the value $F(10) = \ln {11}.$

[[ (added 4 years later) The same example with $b = 7$ is an answer to a similar question in Mathematics Stack Exchange --- Problems that become easier in a more general form. This other question has several answers different from any of those given here, and thus it is worth looking at for more examples pertaining to the present question. ]]

You can find this method discussed in older (say, before 1945) advanced calculus texts. This is also the method Feynman talks about in his book Surely You're Joking Mr. Feynman (excerpt below). I used the example above on take home tests in the late 1990s when I was teaching at a residential "math-science high school academy". The problem was supplied with a generous hint, and I also included the Feynman quote below. [[ (Added 4 years later) See problem #5 on this take home test for the last time I assigned this problem. ]] Later (8 April 2000) I posted this in sci.math (see here).

Excerpt from Richard Feynman, Surely You're Joking Mr. Feynman (1985), pp. 86-87. (Text enclosed in brackets, [...], are NOT from the original. These are additions I've included.)

So every physics class, I paid no attention to what was going on with Pascal's Law, or whatever they were doing. I was up in the back with this book: "Advanced Calculus", by Woods. Bader [Feynman's High School Physics teacher, who loaned Feynman his copy of Wood's book] knew I had studied "Calculus for the Practical Man" a little bit, so he gave me the real works--it was for a junior or senior course in college. It had Fourier series, Bessel functions, determinants, elliptic functions--all kinds of wonderful stuff that I didn't know anything about. That book also showed how to differentiate parameters under the integral sign--it's a certain operation. It turns out that [it's] not taught very much in the universities; they don't emphasize it. But I caught on how to use that method, and I used that one damn tool again and again. So because I was self-taught using that book, I had peculiar methods of doing integrals. The result was, when guys at MIT or Princeton had trouble doing a certain integral, it was because they couldn't do it with the standard methods they had learned in school. If it was contour integration, they would have found it; if it was a simple series expansion, they would have found it. Then I come along and try differentiating under the integral sign, and often it worked. So I got a great reputation for doing integrals, only because my box of tools was different from everybody else's, and they had tried all their tools on it before giving the problem to me.

Answer 4

Edit: You might consider Klain and Rota's (1997) proof of Buffon's noodle problem as a somewhat general example that can be used to resolve (the better known) Buffon's needle problem, and also to prove Barbier's Theorem. See more on its wikipage; I came across this example on an old MO post here.

---

Here is a nice problem:

Twenty-three people, each with integral weight, decide to play football, separating into two teams of $11$ people, plus a referee. To keep things fair, the teams chosen must have equal total weight. It turns out that no matter who is chosen to be the referee, this can always be done. Prove that the $23$ people must all have the same weight.

The problem as stated above is $\#3.4.31$ in "The Art and Craft of Problem Solving" (2006, 2e, p. 107) by Paul Zeitz. However, solving it is probably easier when tackling the stronger case for $2n + 1$ people.

N.B. Abstracting away from actual person-weights and extending from positive integers to rational numbers is reasonably straightforward. The result still holds when extended all the way to complex numbers, but this result is tougher to show - and no longer at the level about which you have asked. For a bit of history around this problem, see my earlier MO post here or the blitz summary here.

Answer 5

The proof that it is possible to cover a chessboard with L-shape triominos leaving a space free at the center is a classic. It is proven by induction on the size $2^n \times 2^n$ leaving an arbitrary square free. See e.g. Cut the knot.

Answer 6

Consider two concentric coplanar unit squares (their sides do not have to be coincident).

Show that the area of the region inside both squares is greater than $\frac{3}{4}$.

It's easier if we show something stronger.

The area is greater than $\frac{\pi}{4}$.

Answer 7

An example I just remembered is to compute e.g. $$ \sum_k \binom{n}{k}^2 = \sum_k \binom{n}{k} \binom{n}{n - k} $$ Notice that the variable $n$ appears three times, in such cases it can turn out much easier to separate them: $$ \sum_k \binom{r}{k} \binom{s}{n - k} $$ So a heuristic is to uncouple. Sure, it could be that keeping them the same allows simplifications that aren't applicable if separate, that's why this isn't sure-fire.

And this same example also shows the heuristic of rewriting in an equivalent form (second binomial coefficient in the original).

Answer 8

I think the Squeeze Theorem can provide a good opportunity for this phenomenon. The example I describe below arose in a Real Analysis course for upper-level mathematics majors that I taught this semester, but I can envision similar examples arising in calculus courses.

Exercise: Use the formal definition of convergence of a sequence ("For every $\epsilon>0$ there exists an $N>0$ such that ...") to prove that the $\lim_{n\to\infty} \frac{n^2}{n^4+1}=0$.

The algebra of the desired inequality $-\epsilon<\frac{n^2}{n^4+1}<\epsilon$ can get a little messy. So, when students came to my office hours for assistance with this problem, I used questioning to guide them into realizing that $0<\frac{n^2}{n^4+1}<\frac{n^2}{n^4}=\frac{1}{n^2}$, and then realizing that it is quite easy to use the formal definition to show $\lim_{n\to\infty}\frac{1}{n^2}=0$ and apply the Squeeze Theorem (discussed in class).

I admit this is not quite "prove something stronger", in the sense that the necessary observation is almost trivial (and not really "proving" something), and that observation is arguably not "stronger" than the claimed result to be proven. However, for students who are first learning how to figure out and communicate proofs of this nature ... they certainly need this kind of advice for a problem like this.

Answer 9

Incidentally, I used exactly that heuristic to solve this problem on Math SE, and even remarked on it!

Original: Every integer at least 7 can be written as the sum of distinct primes.
Stronger: Every integer n at least 7 can be written as the sum of distinct primes such that the largest is at most max(11,n−7).

There are other ways to prove the desired theorem without making it stronger, but if one wants to use induction and Bertrand's postulate and no other tools then the heuristic works like magic.