5
$\begingroup$

I was recently thinking about ways in which proof techniques can be combined to yield stronger results, and stumbled across the following combo that is obvious but yet I can't recall seeing an application of it. Basically the combo is using induction to take $\epsilon \rightarrow 0$

Suppose you want to show a statement is true for all $\epsilon > 0$. First show it is true for $\epsilon \ge 1$. Then assume it is true for $\epsilon \ge \frac{1}{k}$, and bootstrap this to show it is true for $\epsilon \ge \frac{1}{k+1}$.

Does anyone know examples of proofs where this technique is used, and if (as I suspect) there are not many examples, why is it so rare?

  • 0
    Yes indeed, it should be $\epsilon \ge 1$ for the base case. Thanks for pointing that out.2012-04-02

1 Answers 1

5

Assuming you mean 'show it is true for $\epsilon \ge 1$' and not 'show it is true for $\epsilon =1$', that is a valid argument. You're right that it is seldom used - I myself have never seen such an argument, though my mathematical career has been a short one. I can't really think of a situation in which it would be easier to prove that a statement was true for all $\epsilon\ge 1$ than it was to prove that it was true for all $\epsilon >0$.

I'll give an example proof though using your argument. Suppose we want to show that the sequence $\frac{1}{n}$ tends to $0$. So we want to show that for all $\epsilon >0$, there exists $N$ such that for all $n\ge N$, $|\frac{1}{n}|<\epsilon$. So we start by proving that this holds for all $\epsilon\ge 1$. That's easy - take $N=2$. All reciprocals of integers beyond $2$ are less than $1$, so we win in that case. Now suppose that we have that for all $n\ge N_k$ and all $\epsilon\ge \frac{1}{k}$, $\frac{1}{n}<\epsilon$ - I've dropped the mod signs because all of these fractions are positive. We know in particular that for all $n\ge N_k$, $\frac{1}{n}<\frac{1}{k}$. So $k. So $k+1. So for all $n \ge N_k+1$, $\frac{1}{n}<\frac{1}{k+1}$, and therefore, $\frac{1}{n}<\epsilon$ for all $\epsilon\ge\frac{1}{k+1}$. So we win.

Having dirty-talked your method a bit, I am now going to have to take back what I said - this has become my new favourite method for proving that $\frac{1}{n} \to 0$ ! Now, I always prefer not to use induction if I don't have to. However, the 'normal' proof of this Theorem - where you take $N$ to be the smallest integer greater than $\frac{1}{\epsilon}$ - actually uses induction implicitly when it assumes that such an integer exists. The assertion that for every real number $x$ there is a natural number greater than $x$ is known as the Archimedean property of the natural numbers, and is proved by induction (or by a 'minimum counterexample' argument, which is equivalent)! Since this property is central to all Theorems to do with convergent sequences, we could in fact argue that all of Analysis is based on inductive arguments. The reason I like your method is that it brings the induction out into the open, rather than hiding it behind the property of Archimedes. However, most mathematicians prefer to keep the induction implicit, as it makes for shorter proofs. I think that is the main reason why you never see arguments of the type you describe.

A little note to end on - there is a form of 'continuous induction' that can be quite useful. If we know that a statement $P(k)$ is true when $k and we know that if $P(k)$ is true for all $k then there is some $\epsilon>0$ such that $P(k)$ is true for all $k, then we know that $P(k)$ is true for all $x \in \mathbb{R}$. Why? Assume on the contrary that there is some $y \in \mathbb{R}$ such that $P(y)$ is untrue. Now let $S$ be $\{x:P(k) \textrm{ is true for all } k < x \}$. Now $S$ is bounded above by $y$, so it has a least upper bound $z$. But then $P(k)$ is true for all $k, so it is true for all $k for some $\epsilon>0$, contradicting $z$ being an upper bound for $S$.

  • 0
    Interesting response, thanks. I was hoping there were some "standard" proofs with the technique though it looks like perhaps there aren't.2012-04-02