# On building a subsequence inductively

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?

-

## 3 Answers

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\}\;.$$

-
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

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$.

-

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$.

-