## Prove a more general theorem

Often when you try to prove something, it is easier prove a stronger statement. Many of the examples of this, are statements that are proven by induction. E.g. define the sequence of functions $f_n:\mathbb{R}\to\mathbb{R}$ by $f_1(x)=x^2-1$ and $f_n(x)=f_{n-1}(f_1(x))$ for $n\geq 2$. Prove that $f_n$ has $n+1$ real roots (inspired by problem 2 day 1  IMC 2004).

When solving this problem, it helps to find a stronger statement, that is true for all n, because that gives you a stronger induction hypothesis, so that you can make the induction step. But sometimes, this is not enough, and you have to “invent” (or should I say discover?) other cases. Let me give an example of this:

Problem 5 day 1 IMC 1999: Suppose that $2n$ points of a $n\times n$ grid are marked. Show that for some $k > 1$ one can select $2k$ distinct marked points, say $a_1,...,a_{2k}$, such that $a_{2i-1}$ and $a_{2i}$ are in the same row, $a_{2i}$ and $a_{2i+1}$ are in the same column, $\forall i$, indices taken mod $2k$.

We have $2n$ point and $n$ rows and $n$ columns, so on average there is $2$ points in each row and in each column. If we knew that there was at least two points in each row and column, the problem would be easy: We could just start at one point, go to a point in the same row,  then to a point in the same column, and so on. Continue to do this (you can do that, because there is a least two points in each row and column), until you hit a point you have visited before, and you have a loop (if you both began and ended with a “row-move” or with “column-moves”, you can just “jump over” the first point). But unfortunately, there could be rows or columns with only one point or none points at all. If there is both a row and a column with at most 1 point in each, we can delete this row and column, and we have a problem with a $(n-1)\times (n-1)$ grid and at least $2(n-1)$ marked points. This gives us a hope, that we can prove the statement by induction. But what if all rows contains 2 marked points, but some columns only contain 1? If we delete a column, we would get a $n\times (n-1)$ grid with $2n-1$ marked points, so this suggests that we should try to prove something stronger:

Stronger statement: Let $n+m$ points of a $n\times m$ grid be marked. Now for some $k > 1$ you can select $2k$ distinct marked points, $a_1,...,a_{2k}$, such that $a_{2i-1}$ and $a_{2i}$ are in the same row, $a_{2i}$ and $a_{2i+1}$ are in the same column, $\forall i$, indices taken mod $2k$.

Proof: By induction on n and m. This is true if $n=1$ or if $m=1$ because you can’t choose $m+1$ points in a $1\times m$ grid. If we have two point in every row and column, we can just use the above proof, if not, we delete a row or column with at most one point, and thereby reduces the problem to a smaller one.

Here is another IMC problem, you can try to solve:

Problem 5 day 1 IMC 2004: Let $S$ be a set of $\displaystyle { 2n \choose n } + 1$ real numbers, where $n$ is a positive integer. Prove that there exists a monotone sequence $\{a_i\}_{1\leq i \leq n+2} \subset S$ such that $|x_{i+1} - x_1 | \geq 2 | x_i - x_1 | ,\text{for all } i=2,3,\ldots, n+1$

Update: Here are two MathOverflow questions about this subject, where you can find more examples

Explore posts in the same categories: Problem solving

Tags: , ,

You can comment below, or link to this permanent URL from your own site.

### One Comment on “Prove a more general theorem”

1. Danilo Says:

Skype has launched its online-based consumer beta for the
entire world, right after introducing it extensively in the Usa and U.K.
previous this four weeks. Skype for Website also now facilitates Chromebook and Linux for instant text messaging conversation (no video and
voice nevertheless, those need a connect-in installation).

The expansion of your beta provides assistance for a
longer selection of different languages to help
you reinforce that worldwide usability