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

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.

• – dtldarek May 5 '14 at 15:09
• Great question, looking forward to the answers. – Mark Fantini May 5 '14 at 16:25
• Offhand I am reminded of this problem about an $8 \times 8$ chessboard: matheducators.stackexchange.com/a/1255/262 In this case (or perhaps if the question were about a $32 \times 32$ board instead...) it seems easiest to use induction on all $2^n \times 2^n$ boards. – Benjamin Dickman May 5 '14 at 17:15
• Moreover, any theorem (or group of propositions) provides a potential candidate. For example, consider the early facts you prove about limits of convergent sequences (involving addition, subtraction, multiplication, division...) and then consider how much easier these make what might have been a very involved $\delta-\varepsilon$ proof otherwise. – Benjamin Dickman May 5 '14 at 17:33

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.

• Sorry for nit-picking, shouldn't that read 'every positive integer is either a prime or can be expressed as a product of primes' ? – smirkingman May 6 '14 at 14:47
• @smirkingman: 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". But I agree that it might be better to be more explicit for people who are not professional mathematicians. – Neil Strickland May 6 '14 at 15:04
• Thanks for the heads-up, I didn't think of 'product of 1 prime'. Solid demonstration of what happens when idiots like me are out of their depth >;-) – smirkingman May 6 '14 at 20:22

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.

• A few months later a similar answer was posted on MSE. It would be helpful to add a comment there linking that to here, since this answer has more details, and doing so serves to link these related pages (I can't do so now). – Bill Dubuque May 12 '18 at 23:43
• @Number: Thanks for the observation and suggestion. I used the opportunity to also link to an old test of mine that I happened once to have posted at Math Forum, a test on which this integral appeared. (For a few years, Math Forum allowed documents to be uploaded to their discussion groups, and during this time I put up 25 to 40 of mine in various posts. Most of them, maybe all ... I don't know, can be found using this search, if anyone is interested.) – Dave L Renfro May 13 '18 at 0:37
• We still need a link from MSE to here - that's what I was recommending. The link I gave in my comment (and that in your answer) won't show in the Linked section on the MSE question because it is cross-site. A comment on the MSE answer would do the trick. – Bill Dubuque May 13 '18 at 1:06
• @Number: Oh, I didn't realize Stack Exchange linked questions in a one-directional manner. I'll take care of the other direction right now. – Dave L Renfro May 13 '18 at 8:55

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.

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.

• I was going to ask "why only integers", and then I see your N.B. and you blow me away with the complex number result. – Joe Z. May 5 '14 at 23:38
• @JoeZ. While the quoted problem is (more) easily solved by generalizing first, it is the specific result over $\mathbb{Q}$ that can be used to prove the most general version over $\mathbb{C}$. (As the answerer at my first MO link remarks: "the result can be deduced from the rational case.") – Benjamin Dickman May 6 '14 at 0:36

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.

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

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.