13
$\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$
32
$\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
  • $\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
    Sep 23 '17 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$ Sep 23 '17 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$ Sep 23 '17 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
    Sep 24 '17 at 4:27
10
$\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
    Sep 23 '17 at 18:09
  • 1
    $\begingroup$ @Saad You are now confusing sequences with series. $\endgroup$ Sep 23 '17 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
    Sep 24 '17 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$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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