34
$\begingroup$

Especially (but not only) in the case of induction proofs, it happens that a stronger claim $B$ is easier to prove than the intended claim $A$ (e.g. since the induction hypothesis gives you more information). I am trying to come up with exercises for beginner students that help to demonstrate this point (and also interested in the general phenomenon). Do you know any good examples (preferably elementary ones) where strengthening a claim makes the proof easier?

Here is an example of what I mean (Problem 16 from chapter 7 of Engel's `Problem solving strategies'):

Show that $\frac{1}{2}\frac{3}{4}...\frac{2n-1}{2n}\leq\frac{1}{\sqrt{3n}}$ for $n\geq 1$. This is much harder than proving the stronger statement that $\frac{1}{2}\frac{3}{4}...\frac{2n-1}{2n}\leq\frac{1}{\sqrt{3n+1}}$ for $n\geq 1$, which is a straightforward induction.

$\endgroup$
  • $\begingroup$ You might want to ask this on MESE too. $\endgroup$ – Git Gud Nov 5 '14 at 11:38
  • $\begingroup$ Indeed. Great page. Thanks for the suggestion! $\endgroup$ – M Carl Nov 5 '14 at 11:43
  • 7
    $\begingroup$ The sum of the first $n$ cubes is a perfect square. $\endgroup$ – bof Nov 5 '14 at 12:08
  • 5
    $\begingroup$ Duplicate: math.stackexchange.com/questions/899109/… $\endgroup$ – Qiaochu Yuan Nov 9 '14 at 6:35
  • 3
    $\begingroup$ I'm not sure I agree that it's a duplicate. I guess they're technically equivalent, but proving a generalization isn't spiritually the same as having to prove a bunch of stuff in order to get something smaller- like driving all over the city just to go one block, because the road was closed. At least that is my opinion, after some thought. $\endgroup$ – Alexander Gruber Nov 15 '14 at 2:33

15 Answers 15

16
$\begingroup$

Here's my favorite proof - for the reasons that it's very easy and elementary enough that it takes almost no mathematical knowledge at all - for an example of the general case that is easier than the special case:

Problem: For every $2^n\times2^n$ grid where $n$ is a natural number, there is a covering with $L$ shaped pieces, all have an area of $3$ squares, that leaves one central square (one of four central squares) empty.

Here is an example for $n=2$:

problem

General case is:

Problem: For every $2^n\times2^n$ grid where $n$ is a natural number, there is a covering with $L$ shaped pieces, all have an area of $3$ squares, that leaves only one arbitrarily specified square empty.

General case claims that we can choose any square (not necessarily center as opposed to special case) we want to be empty, before covering. Proof is very easy and uses induction on $n$:

Let $P(n)$ be the proposition that problem states.

Base case: $P(0)$ is obvious.

Inductive step: Assume $P(n)$ for some $n\in\mathbb{N}$. Take any $2^{n+1}\times2^{n+1}$ board and arbitrarily choose one square which will be empty. Divide the board four $2^n\times2^n$ quadrants. From hypothesis; there is a covering of the quadrant which has chosen square on it, and covering of all other quadrants except three center squares of the big square like this:

solution

Here, red is chosen square and blues are empty squares for other quadrants. Now, put one piece on blue squares and you have $P(n+1)$. $\blacksquare$

For me; this argument is also very effective way to make people, who have little or no mathematical experience, to comprehend that sometimes why and how proving general case may be easier than special one. Therefore make an excellent example to demonstrate this point for beginner students.

$\endgroup$
  • 1
    $\begingroup$ @columbus8myhw, i don't know any easier proofs of the special case. Which proof have you come up with? $\endgroup$ – Alistair Jul 28 '15 at 1:26
12
+100
$\begingroup$

Here's my favorite. Let $(a,n)=1$. Then there are infinitely many primes $p \equiv a \pmod{n}$, and with analytic density $\frac{1}{\phi(n)}$. This is easier to prove (in general) than just showing a single prime $p \equiv a \pmod{n}$ exists, since as far as I know there is no general way to just find a single one without just finding them all with the proper density. If you go looking for just a single one you'll probably get stuck.

$\endgroup$
  • $\begingroup$ Even without the analytic density value, by stating the result in the generality of all $a$ and $n$ with $(a,n) = 1$ it turns out that proving the existence of one prime $p \equiv a \bmod n$ really proves the existence of infinitely many! The point is that you can adjust the modulus and remainder (e.g., change $n$ to a power of $n$) and re-apply the existence of a single prime in a new case (different modulus and remainder) to get a new prime that still fits the original congruence. See Theorem A.1 in kconrad.math.uconn.edu/blurbs/ugradnumthy/…. $\endgroup$ – KCd May 9 at 21:12
9
$\begingroup$

Here are two examples which might be useful

  • Example 1: Generalize in order to use techniques from analysis resp. formal operator techniques

Problem: Evaluate

$$\sum_{k=1}^{n}\frac{k^2}{2^k}$$

This can be done by instead evaluating

$$\sum_{k=1}^{n}k^2x^k$$

For $x\neq 1$ we know that

$$S(x)=\sum_{k=1}^{n}x^k=\frac{1-x^{n+1 }}{1-x}$$

Now differentiating each side and multiplying with $x$ we get

\begin{align*} (xD)S(x)&=\sum_{k=1}^{n}kx^{k}\\ &=(xD)\frac{1-x^{n+1 }}{1-x}\\ &=\left(1-(n+1)x^n+nx^{n+1}\right)\frac{x}{\left(1-x\right)^2} \end{align*}

Differentiating again each side and multiplying with $x$ we get

\begin{align*} {(xD)}^2S(x)&=\sum_{k=1}^{n}k^2x^{k}\\ &=(xD)^2\frac{1-x^{n+1 }}{1-x}\\ &=\left(1+x-(n+1)^2x^n-(2n^2+2n-1)x^{n+1}-n^2x^{n+2}\right)\frac{x}{\left(1-x\right)^3} \end{align*}

We conclude

\begin{align*} S\left(\frac{1}{2}\right)&=\sum_{k=1}^{n}\frac{k^2}{2^k}\\ &=\left(\frac{3}{2}-(n+1)^2\frac{1}{2^n}-(2n^2+2n-1)\frac{1}{2^{n+1}}-n^2\frac{1}{n+2}\right)\cdot 4\\ &=6-\frac{1}{2^n}\left(n^2+4n+6\right) \end{align*}


Another example where generalization is useful

  • Example 2: Generalize integrals by introducing a parameter and use the technique of parameter differentiation

Problem: Evaluate

$$\int_{0}^{\infty}\frac{\sin^2 x}{x^2}dx$$

given that $\int_{0}^{\infty}\frac{\sin x}{x}dx=\frac{1}{2}\pi$.

The idea is to introduce a parameter and evaluate the more general integral

\begin{align*} I(a)=\int_{0}^{\infty}\frac{\sin^2 (ax)}{x^2}dx,\qquad a\geq 0\tag{1} \end{align*}

and use parameter differentiation.

Differentiating each side of (1) with respect to $a$, we get

\begin{align*} I^{\prime}(a)&=\int_{0}^{\infty}\frac{2\sin (ax)\cos (ax)\cdot x}{x^2}dx\\ &=\int_{0}^{\infty}\frac{2\sin (2ax)}{x}dx\\ \end{align*} Now substituting $y=2ax$, we get $dy = 2a dx$, and \begin{align*} I^{\prime}(a)&=\int_{0}^{\infty}\frac{\sin y}{y}dx=\frac{1}{2}\pi\\ \end{align*}

Integrating each side gives

$$I(a) =\frac{1}{2}\pi a+C,\qquad C \text{ constant}$$

Since $I(0)=0$, we get $C=0$. Thus $I(a)=\frac{1}{2}\pi a, a\geq 0$. Setting $a=1$ yields

$$I(1)= \int_{0}^{\infty}\frac{\sin ^2 x}{x^2}dx = \frac{1}{2}\pi$$


Note: The examples above can be found in Problem-Solving Through Problems. They are stated as problems 1.12.1 and 1.12.3 in chapter 1.12 Generalize.

$\endgroup$
  • $\begingroup$ For your last example, an integration by part gives the result immediatly $\endgroup$ – mvggz Nov 14 '14 at 8:24
8
$\begingroup$

Here is a relevant (albeit somewhat simplistic) example from the representation theory of finite groups.

An orbit of a finite group $G$ on a finite vector space $V$ is a set $v^G=\{v^g:g\in G\}$. (Here, I'm using "group theorist notation," where $v^g$ denotes $g$ acting on $v$. It's what you usually see written as $v\cdot g$ or $g\cdot v$ in algebra textbooks.) A regular orbit on $V$ is an orbit such that $\left|v^G\right|=\left|G\right|$. So, by Orbit-Stabilizer, we have that $\left[G:\operatorname{Stab}_G(v)\right]=\left|G\right|$, which means that $\operatorname{Stab}_G(v)=1$. Saying that $G$ has a regular orbit on $V$ is, therefore, equivalent to finding some element of $V$ that is fixed only by the identity. Determining when groups have regular orbits is a well-studied problem in group theory, about which there are many open conjectures.

One would think that it would be easier to find one regular orbit on $V$ than to count all the not-regular orbits instead. However, in practice, we often find ourselves showing that $$\left|\bigcup_{1\ne g\in G}\mathbf{C}_V(g)\right|< \left|V\right|$$ So, we're saying, "Look at all these vectors that aren't part of regular orbits! As you can see, there's still room left in $V$, so the remaining orbits must be regular."

To deal with the left hand side, we must explicitly compute all these fixed point sets, determine their intersections, apply inclusion-exclusion, and so on. What we get is much more information about the group than the regular orbit we originally sought for, but in many cases, a simpler method is not known.

$\endgroup$
6
$\begingroup$

The standard proof that Buffon's needle technique to compute $\pi$ works is needlessly complicated. It's much easier to solve the seemingly harder problem of Buffon's noodle.

enter image description here

In the case of Buffon's needle, a needle of length $l$ is thrown onto a floor ruled with parallel lines $t$ apart. We want the probability it crosses a line. The standard argument is at Wikipedia and requires integrating trig functions to get $2l/(tπ)$. That leads to the well know Monte Carlo method to compute $π$.

With Buffon's noodle we throw a 2-dimensional curve onto the floor and want the expected number of crossings. Think of the curve as being a sequence of short straight line segments of equal length. The expected number of crossings is the sum of the expected value of the crossings for each segment. Each short segment has the same geometry (ie. it's a short straight line) so all we need is the expected number of crossings for a segment which is effectively the same as knowing the number of crossings per unit length. We can get this constant easily. If you throw a circle of diameter $t$ we expect it to cross in 2 places. So we expect $2/(π t)$ crossings per unit length.

This tells us immediately that we have probability $2l/(\pi t)$ of a crossing from a needle of length $l<t$ because such a needle has $0$ or $1$ crossings and the probability is therefore the expected number of crossings.

The harder problem was much easier to solve. In my opinion this is one of the most beautiful arguments in mathematics.

As a side effect you get Barbier's theorem too.

$\endgroup$
4
$\begingroup$

Thomassen's beautiful proof that every planar graph is 5-choosable actually proves that planar graphs satisfy a stronger list-coloring property, using this stronger statement as its induction hypothesis.

$\endgroup$
  • 2
    $\begingroup$ For that matter, Thomassen's proof may be the simplest proof that planar graphs are $5$-colorable. $\endgroup$ – bof Nov 16 '14 at 10:39
4
$\begingroup$

Two induction examples:

Example 1:

$$\sum_{k=1}^n \frac{1}{k^2} <2$$

This doesn't work by induction, can be proven by some other techniques. But

$$\sum_{k=1}^n \frac{1}{k^2} <2-\frac{1}{n}$$

is a trivial exercise.

Example 2: Any tree with at least two vertices has at least a leaf.

This again doesn't work by induction, can be proven after one learns some basic facts about trees. But again,

Any tree with at least two vertices has at least two leafs.

is a trivial induction exercise, which only uses the definition of a tree.

$\endgroup$
4
$\begingroup$

Perhaps not the most squarely on-the-mark example, but an exercise requesting a proof of the irrationality of $e-\sqrt{2}$ or similar had me stymied (I was young and had lived a sheltered, analysis-centric life). I shelved it, looked at it the next day, misread 'irrational' as 'transcendental', and went 'Uh... Oh yeah!'

$\endgroup$
3
$\begingroup$

Actually, "easier to prove more" is the rule in mathematics rather than the exception. Generally, the trick to proving a hard theorem is to find the right strengthening which is easier to prove. Sometimes the stronger statement is memorable and quotable (as in the examples we're likely to see in answers to this question), often they are not.

For example, Sperner's lemma, the one useful for proving Brouwer's fixed point theorem. You want to prove that every Sperner labelling has at least one complete simplex, but the way to prove that (as far as I know) is to prove the stronger assertion, that every Sperner labelling has an odd number of complete simplices.

An example from general topology.

Hard Theorem: There are two Lindelöf spaces whose product is not Lindelöf.

Stronger and easier: The real line with the half-open interval topology is a Lindelöf space whose square is not Lindelöf.

Stronger still and easier yet: The real line with the half-open interval topology is a Lindelöf space $X$, and the set $S=\{(x,-x):x\in X\}$ is an uncountable discrete closed subset of $X\times X$.

$\endgroup$
  • 2
    $\begingroup$ 'Actually, "easier to prove more" is the rule in mathematics rather than the exception.' Fully agreed. The (stronger) statement that a list of assumptions proves the conjunction of that list is always easier to show than the (weaker) statement that a list of assumptions proves something that is actually interesting. $\endgroup$ – goblin Nov 16 '14 at 12:15
3
$\begingroup$

Not sure if it's exactly the kind of thing what you're after, but of the two problems

Describe all pairs $(A,B)$ of $n\times n$ matrices such that $AB = A+B$.

and

Describe all pairs $(A,B)$ of elements in any ring such that $AB = A+B$.

the second, more general, one is easier because you don't get distracted by all your irrelevant knowledge of matrices.

$\endgroup$
  • $\begingroup$ I've thought about this one for a little while but the answer doesn't immediately jump out at me. Mind giving a hint? $\endgroup$ – Cameron Williams Jul 26 '15 at 2:51
  • 3
    $\begingroup$ @CameronWilliams : Hm. Hard to give a hint for this one without giving the whole thing. Maybe this? $AB-A-B$ almost factors. $\endgroup$ – user21467 Jul 26 '15 at 14:12
  • $\begingroup$ Oh duh of course. I was thinking of higher power relations. Thanks! $\endgroup$ – Cameron Williams Jul 26 '15 at 14:55
  • $\begingroup$ I think the condition reduces to them commuting, but strictly speaking my solution requires the 'almost factors' to be invertible? (or in terms of matrices, the space being finite dimensional) Are we thinking of the same argument? $\endgroup$ – Vandermonde Aug 11 '15 at 19:09
3
$\begingroup$

Simple examples appear on this site quite often. Most recently Density of computable numbers asks if every real number is arbitrarily close to a computable number. Computable numbers are notoriously difficult to reason about, but in this case there is an easy path to the solution: every real number is arbitrarily close to a rational number, which is sufficient.

A very similar example is Is $\pi$ approximately algebraic?. The question asks if there is a sequence of algebraic numbers that approaches $\pi$. $\pi$ is very difficult to handle, and algebraic numbers can be tricky, but in this case the answer again follows from something very simple: rational numbers are algebraic, $\pi$ is real, every real number can be approximated by rationals, so a fortiori $\pi$ can be approximated by algebraic numbers.

$\endgroup$
3
$\begingroup$

There is an immense family of examples where “There exists $x$ with property $P$” is more difficult to prove than the strictly stronger statement “$c$ has property $P$”. In many cases the only way we can prove the first of these is by constructing a specific $c$ for which $P$ holds; coming up with $c$ might be the only difficult part of the proof.

To take an easy example, consider

There exist topological spaces $A, B, C$ with $A× C \cong B× C$ but $A\not\cong B$.

as compared with

$\{0,1\}×\Bbb Z \cong \{0\}×\Bbb Z$ but $\{0,1\} \not\cong \{0\}$.

To prove the former may require some thought to come up with the simple example in the latter, but once you do the proof is trivial.

Or another example, mentioned elsewhere in this thread:

There exist Lindelöf spaces $A$ and $B$ whose product is not Lindelöf

could be hard, if you don't know the counterexample, but

The Sorgenfrey line $L$ is Lindelöf but $L^2$ is not

is straightforward.

Many famous mathematical examples are of this type. For example, the paradoxical decomposition of the Banach-Tarski paradox, or the exotic 7-spheres, or Gödel sentences, or Ackermann's function, or Dirichlet's function, and so on. Each one is an answer to a difficult-seeming question "Does there exist an object with bizarre property $P$”, and the difficulty is mainly in constructing the object in the first place, less so with proving that the constructed object has property $P$.

$\endgroup$
2
$\begingroup$

A simple example: it's often easier to prove that a given sequence converges to a specific limit than to prove convergence without identifying the limit.

$\endgroup$
1
$\begingroup$

Does the square or the circle have the greater perimeter? A surprisingly hard problem for high schoolers is a good example from an immense family of similar examples.

square and circle diagram

The easiest way to prove that the square has a greater perimeter is to calculate the perimeters explicitly, proving not merely that the square is larger but that the ratio of the perimeters is exactly $\frac{16}{5\pi}$.

$\endgroup$
0
$\begingroup$

Let $\ell^2$ be the set of all square-summable sequences $\{a_n\}$, i.e., those sequences such that $\sum |a_n|^2 < \infty$.

Instead of showing that the Cauchy-Schwarz inequality $|\sum a_n\overline{b_n}|^2 \le \sum |a_n|^2\cdot \sum |b_n|^2$ holds by considering partial sums, show instead that $\ell^2$ equipped with the map $\langle a_n,b_n\rangle = \sum a_n\overline{b_n}$ is an inner product space, i.e., that $\langle\cdot,\cdot\rangle$ is an inner product. This involves checking the four or so conditions that define an inner product, each of which is a much simpler task.

The Cauchy-Schwarz inequality is valid in any inner product space, hence the claim.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.