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.

Let $(s_n)$ be a sequence of real numbers and suppose that lim sup $ s_n =+ \infty$. I want to inductively build a subsequence $(s_{n_k})$ in $(s_n)$ such that lim $s_{n_k}=+\infty$. What would be my base case and inductive hypothesis?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

I don’t really like using the terms base case and inductive hypothesis for recursive constructions, as distinct from proofs by induction. What corresponds to the base case of an induction is simply the choice of the first element of the subsequence. You can start anywhere, so you might as well let $k_0=0$: the subsequence will have the same first term as the original sequence.

What corresponds to the induction step is specifying how to choose a term of the subsequence when you’ve chosen all of the earlier terms. You need to be sure to accomplish two things with this choice. First, you need to make the subsequence diverge to $\infty$. One simple way to do that is to make sure that $s_{n_k}\ge k$ for each $k\in\Bbb N$.

The other thing that you need to worry about is making sure that $n_{k+1}>n_k$ for each $k\in\Bbb N$, so that you actually get a subsequence. Thus, given $n_k$ for some $k\in\Bbb N$, just let

$$n_{k+1}=\min\{n\in\Bbb N:n>n_k\text{ and }s_n\ge k+1\}\;.$$

share|improve this answer
    
Hey Brian, I'm a little confused as to why you would take the minimum of those integers in choosing $n_{k+1}$. –  Ernest Singleton Jan 30 '13 at 4:30
    
@Ernest: Minimality isn’t crucial: any integer in the set would work. But it’s a nice way to make a specific, well-defined choice. –  Brian M. Scott Jan 30 '13 at 4:32
    
Oh. I was just misinterpreting your notation. But I think I understand now: you are just saying we should take $n_{k+1}$ to be the smallest integer such that both those conditions are satisfied. –  Ernest Singleton Jan 30 '13 at 4:34
    
@Ernest: Yes, that’s right. –  Brian M. Scott Jan 30 '13 at 4:43
    
Alternatively, if the lim sup of a sequence diverged to $-\infty$, could we prove that this sequence had a subsequence that diverged to $-\infty$ by ensuring that $s_{n_k}$ is less than $k$, for every $k$? –  Ernest Singleton Jan 30 '13 at 5:00
show 3 more comments

Since the $\limsup s_n=\infty$, for each $k\in\Bbb N$, define $$s_{n_k}=\inf\{s_n:\ s_n\geq k\}.$$ Now it's clear this is a monotone increasing sequence, hence $\lim_{k\to\infty}s_{n_k}=\infty$.

share|improve this answer
add comment

We define the sequence $(n_k)$ of indices inductively as follows.

Let $n_1=1$. For any integer $k\gt 1$, let $n_k$ be the smallest index $i$ such that $s_i\gt k$ and $i\gt n_j$ for all $j\lt k$.

It is not hard to show from the $\limsup$ condition that there is such an $i$. That the subsequence goes to infinity follows from the fact that $s_{n_k}\gt k$ if $k\gt 1$.

share|improve this answer
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.