Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
In most induction proofs the method involves inducing the $n$th case from previous ones. The key idea is that there is a decomposition from the larger case into smaller ones. I'm not sure that logic holds for many cases when trying to prove for $\epsilon\to0$. I can't think of a natural way to deduce "since the proposition holds for this small $\epsilon$, it must hold for a smaller value". –  davin Mar 31 '12 at 10:48
1  
Just one quick point - surely you need to show that it's true for $\epsilon\ge 1$ not $\epsilon=1$ in the base case. –  Donkey_2009 Mar 31 '12 at 11:02
    
Yes indeed, it should be $\epsilon \ge 1$ for the base case. Thanks for pointing that out. –  Nick Alger Apr 2 '12 at 6:24
add comment

1 Answer 1

up vote 5 down vote accepted

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<n$. So $k+1<n+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<a$ and we know that if $P(k)$ is true for all $k<x$ then there is some $\epsilon>0$ such that $P(k)$ is true for all $k<x+\epsilon$, 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<z$, so it is true for all $k<z+\epsilon$ for some $\epsilon>0$, contradicting $z$ being an upper bound for $S$.

share|improve this answer
    
Interesting response, thanks. I was hoping there were some "standard" proofs with the technique though it looks like perhaps there aren't. –  Nick Alger Apr 2 '12 at 6:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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