15
$\begingroup$

For example, if I have the sequence $(1,2,3,4,5,6,7,8,\ldots)$ i.e $x(n) = n$ for all natural numbers, then is the subsequence $(1,1,1,1,1...)$ valid? Or can I only take one element from the sequence once? Would the subsequence $(1,2,1,2,1,2...)$ be a valid subsequence?

Thanks.

$\endgroup$

6 Answers 6

36
$\begingroup$

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements

Formally, a subsequence of the sequence $(a_n)_{n \in \mathbb{N}}$ is any sequence of the form $(a_{n_k})_{k \in \mathbb{N}}$ where $(n_k)_{k \in \mathbb{N}}$ is a strictly increasing sequence of positive integers.

Hence, your two examples are not valid, as $1$ appears exactly once in the original sequence.

However if the original sequence is $(1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,\ldots)$ that is the $8$ numbers are periodic, then yes, it is a valid subsequence.

$\endgroup$
4
  • 1
    $\begingroup$ Thank you. You mentioned 'without changing the order of the remaining elements'. What does that mean? Does it mean (5,1,3,7,9....) is not a valid subsequence, since we made the 5 appear before the 1 and 3? Also, yes, I did intend it to be an increasing sequence of positive integers. $\endgroup$
    – John
    Commented Sep 23, 2017 at 17:51
  • 1
    $\begingroup$ yup, in the original sequence $5$ appears after $1$, hence the ordered need to be kept that way. a valid subsequence is $(1,3,5,7,9,\ldots)$. $\endgroup$ Commented Sep 23, 2017 at 17:52
  • 2
    $\begingroup$ +1 Note: most of the time "subsequence" means "infinite subsequence" so you have to keep infinitely many of the elements. $\endgroup$ Commented Sep 23, 2017 at 17:57
  • $\begingroup$ @Saad I think that another way to look at it (which is what this answer is saying in the less formal initial definition) is that if you imagine writing out your entire sequence (which you can't really do in practice but you can imagine what that would look like if you could) and then crossed out some (possibly an infinite number) of terms, what you would be left with is a subsequence. A pointed out by Ethan Bolker, you can't leave just a finite number of terms, but you could still cross out an infinite number of them (every other term for example). $\endgroup$
    – Matthew
    Commented Sep 24, 2017 at 4:27
12
$\begingroup$

A sequence of real numbers is a map $x:\Bbb N\to\Bbb R$; we typically write it as $n\mapsto x_n$ (rather than $n\mapsto x(n)$).

A subsequence of this sequence is a map $y=x\circ\phi$ where $\phi:\Bbb N\to \Bbb N$ is a strictly increasing map. Then $y_n=x_{\phi(n)}$. Neither of your examples is a subsequence of your given sequence which has $x_n=n$.

$\endgroup$
3
  • $\begingroup$ Thanks. Could you explain why the order of terms is preserved if ϕ is a strictly increasing map? i.e If I have the harmonic series, (1+1/2+1/3... ) and then I take the map ϕ(n) = 2^n, why does that guarantee that the order of terms is preserved? I'm just trying to get some intuition for why we need a strictly increasing map. $\endgroup$
    – John
    Commented Sep 23, 2017 at 18:09
  • 1
    $\begingroup$ @Saad You are now confusing sequences with series. $\endgroup$ Commented Sep 23, 2017 at 18:12
  • $\begingroup$ Sorry, I meant the sequence (1,1+1/2,1+1/2+1/3,... ), and then forming the subsequence (1+1/2,1+1/2+1/3+1/4,1+1/2+1/3+1/4+1/5+1/6+1/7+1/8,..) $\endgroup$
    – John
    Commented Sep 24, 2017 at 1:33
7
$\begingroup$

This may be easier to visualize: Write your sequence (any sequence) $$7,8,5,6,4,4,5,7,7,7,7,8,7,3,2,6,1,2,6,2,8,3,3,2,3,\ldots$$ Then select some elements $$7,\underline{8},5,6,\underline{4},4,5,\underline{7},7,7,7,8,\underline{7},3,\underline{2},6,\underline{1},\underline{2},6,\underline{2},8,3,\underline{3},2,3,\ldots$$ and erase the rest $$8,4,7,7,2,1,2,2,3,\ldots$$ That is a subsequence...

$\endgroup$
3
$\begingroup$

No.

A subsequence is a sequence taken from the original, where terms are selected in the order they appear.

For example, let $x_n = \frac{1}{n}$. Let's take a subsequence $x_{n_j}$ where we pick every other term, i.e.

$$ x_{n_j} = \left(1, \frac{1}{3}, \frac{1}{5}, \frac{1}{7}, \ldots \right) $$

Notice how these terms in the subsequence are taken in the order they appear.

$\endgroup$
3
$\begingroup$

Consider a sequence $$a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8, \dots$$

Intuitively, we can create a subsequence by selecting an infinite amount of random terms of this sequence, and throwing what's left away. However, it is important that if we select $a_i$ and $a_j$ with $i <j$, then also $i < j$ in the subsequence. In other words: we keep the order of the elements in the original sequence.

For example, the sequence:

$$a_1,a_3,a_4,a_7, \dots$$ would be a subsequence of the sequence written earlier.

In this case, we can then find a strictly increasing function $k: \mathbb{N} \to \mathbb{N}$ such that $$1 \mapsto 1$$ $$2 \mapsto 3$$ $$3 \mapsto 4$$ $$4 \mapsto 7$$ $$\dots$$

and write $b_n = a_{k_{n}}$ to denote the subsequence .

The strictly increasing part is important to preserve the order of the elements as in the original sequence.

This leads us to the following definition:

A sequence $(y_n)_n$ is subsequence of a function $(x_n)_n$ iff there exists a strictly increasing function $k: \mathbb{N} \to \mathbb{N}$ such that for all $n \in \mathbb{N}$, we have $y_n = x_{k(n)}$

$\endgroup$
2
$\begingroup$

you should not ask whether you can take just one element from the sequence once or not as $(1,1,1,1.....)$ is surely is not a subsequence of $(1,2,3,4,5.....)$ but $(1,1,1,1,1,1.....)$ is subsequence of $(-1,1,-1,1,-1,1.....)$. Hence you should consider your subsequence as if your original sequence is say $\{x(n)\}_{n=1}^\infty$ then your subsequence will be anything of the form $\{x(n_i)\}_{i=1}^\infty$ for some $n_1<n_2<n_3.....$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .