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

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

-

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.

-
(I left this in a comment above...) – Benjamin Dickman May 6 '14 at 3:51

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

-