What is Subsequence: Definition and 60 Discussions

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




A
,
B
,
D



{\displaystyle \langle A,B,D\rangle }
is a subsequence of




A
,
B
,
C
,
D
,
E
,
F



{\displaystyle \langle A,B,C,D,E,F\rangle }
obtained after removal of elements



C


{\displaystyle C}
,



E


{\displaystyle E}
, and



F


{\displaystyle F}
. The relation of one sequence being the subsequence of another is a preorder.
Subsequences can contain consecutive elements which were not consecutive in the original sequence. A subsequence which consists of a consecutive run of elements from the original sequence, such as




B
,
C
,
D



{\displaystyle \langle B,C,D\rangle }
from




A
,
B
,
C
,
D
,
E
,
F



{\displaystyle \langle A,B,C,D,E,F\rangle }
, is a substring. The substring is a refinement of the subsequence.
The list of all subsequences for the word "apple" would be "a", "ap", "al", "ae", "app", "apl", "ape", "ale", "appl", "appe", "aple", "apple", "p", "pp", "pl", "pe", "ppl", "ppe", "ple", "pple", "l", "le", "e", "" (empty string).

View More On Wikipedia.org
  1. H

    Lemma: Extracting a convergent subsequence

    Let's us look at the first implication (I will post the reverse implication once this proof has been verified). We have to prove if there is a subsequence of ##(s_n)## converging to ##t##, then there are infinitely many elements of ##(s_n)## lying within ##\epsilon## of ##t##, for any...
  2. H

    I If a sequence converges, then all subsequences of it have same limit

    Let's say we're given a sequence ##(s_n)## such that ##\lim s_n = s##. We have to prove that all subsequences of it converges to the same limit ##s##. Here is the standard proof: Given ##\epsilon \gt 0## there exists an ##N## such that $$ k \gt N \implies |s_k - s| \lt \varepsilon$$ Consider...
  3. F

    Prove that the sequence does not have a convergent subsequence

    Hello i have problems with this exersice Let $$\{X_{\alpha}\}_{\alpha \in I}$$ a collection of topological spaces and $$X=\prod_{\alpha \in I}X_{\alpha}$$ the product space. Let $$p_{\alpha}:X\rightarrow X_{\alpha}$$, $$\alpha\in I$$, be the canonical projections a)Prove that a sequence...
  4. C

    I ##(a_n) ## has +10,-10 as partial limits. Then 0 is also a partial limit

    Problem: If sequence ## (a_n) ## has ##10-10## as partial limits and in addition ##\forall n \in \mathbb{N}.|a_{n+1} − a_{n} |≤ \frac{1}{n} ##, then 0 is a partial limit of ## (a_n) ##. Proof : Suppose that ## 0 ## isn't a partial limit of ## (a_n) ##. Then there exists ## \epsilon_0 > 0 ## and...
  5. C

    Stuck at proving a bounded above Subsequence

    Summary:: x Let ## \{ a_{n} \} ## be a sequence. Prove: If for all ## N \in { \bf{N} } ## there exists ## n> N ## such that ## a_{n} \leq L ## , then there exists a subsequence ## \{ a_{n_{k}} \} ## such that ## a_{n_{k}} \leq L ## My attempt: Suppose that for all ## N \in {\bf{N}} ##...
  6. evinda

    MHB Sequence has convergent subsequence

    Hello! (Wave) Let $(a_n), (b_n), (c_n)$ sequences such that $(a_n), (c_n)$ are bounded and $a_n \leq b_n \leq c_n$ for each $n=1,2, \dots$ I want to show that $(b_n)$ has a convergent subsequence. I have thought the following: Since $(a_n), (c_n)$ are bounded, $\exists m_1, m_2 \in...
  7. Mr Davis 97

    Every subsequence converges to L implies a_n -> L

    Homework Statement Let ##\{a_n\}## be a bounded sequence such that every convergent subsequence has limit ##L##. Prove that ##\lim_{n\to\infty}a_n = L##. Homework EquationsThe Attempt at a Solution I'm not really understanding this problem. Isn't ##\{a_n\}## a subsequence of itself? So isn't...
  8. Mr Davis 97

    Every convergent sequence has a monotoic subsequence

    Homework Statement Prove that every convergent sequence has a monotone subsequence. Homework EquationsThe Attempt at a Solution Define ##L## to be the limit of ##(a_n)##. Then every ##\epsilon##-ball about L contains infinitely many points. Note that ##(L, \infty)## or ##(-\infty, L)## (or...
  9. L

    A Convergence of a subsequence of a sum of iid r.v.s

    ##X_i## is an independent and identically distributed random variable drawn from a non-negative discrete distribution with known mean ##0 < \mu < 1## and finite variance. No probability is assigned to ##\infty##. Now, given ##1<M##, a sequence ##\{X_i\}## for ##i\in1...n## is said to meet...
  10. S

    Is there a flaw in my longest common subsequence algorithm?

    What I have is /// <summary> /// Provides a solution to the Common Child string problem /// https://www.hackerrank.com/challenges/common-child/problem /// </summary> public static class CommonChild { public static int Solve(string first, string second)...
  11. Eclair_de_XII

    Prove: A bounded sequence contains a convergent subsequence.

    Homework Statement "Let ##\{a_n\}_{n=1}^\infty## be a bounded, non-monotonic sequence of real numbers. Prove that it contains a convergent subsequence." Homework Equations Monotone: "A sequence ##\{\alpha_n\}_{n=1}^\infty## is monotone if it is increasing or decreasing. In other words, if a...
  12. Maddiefayee

    Finding a convergent subsequence of the given sequence

    Homework Statement For some background, this is an advanced calculus 1 course. This was an assignment from a quiz back early in the semester. Any hints or a similar problem to guide me through this is greatly appreciated! Here is the problem: Find a convergent subsequence of the sequence...
  13. T

    Showing Convergent Subsequence Exists

    Homework Statement Consider the space ##([0, 1], d_1)## where ##d_1(x, y) = |x-y|##. Show that there exists a sequence ##(x_n)## in ##X## such that for every ##x \epsilon [0, 1]## there exists a subsequence ##(x_{n_k})## such that ##\lim{k\to\infty}\space x_{n_k} = x##. Homework Equations N/A...
  14. O

    MHB Cauchy sequence and subsequence

    Let $\left\{{x}_{n}\right\}$ be a sequence...İf $\left\{{x}_{2n}\right\}$ is caucy sequence, can we say that $\left\{{x}_{n}\right\}$ is cauchy sequence ?
  15. S

    Does Convergence in the Mean Imply Ordinary Convergence?

    Homework Statement 1. Consider the sequence $$\frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{2}{4}, \frac{3}{4}, \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5},\frac{1}{6}, \ldots$$ For which values ##z \in \mathbb{R}## is there a subsequence converging to ##z##? 2. Prove that...
  16. D

    Sequence and subsequence - real analysis

    Hello, Solving last exam and stuck in this exercise Homework Statement Consider an increasing sequence {xn} . We suppose ∃ x∈ℝ and {xnk} a sebsequence of {xn} and xnk→x a/ Show that for any n∈ℕ , ∃ k∈ℕ as n≤nk b/ Show that xn→x Homework Equations 3. The Attempt at a Solution [/B] For b/ it...
  17. C

    Every sequence has a convergent subsequence?

    I'm not sure if this is true or not. but from what I can gather, If the set of Natural numbers (divergent sequence) {1, 2, 3, 4, 5,...} is broken up to say {1}, is this a subsequence that converges and therefore this statement is true?
  18. evinda

    MHB Sentences about Greatest Common Subsequence

    Hello! (Wave) Let $X=<x_1,x_2, \dots , x_m>$ and $Y=<y_1,y_2, \dots, y_n>$ be sequences and let $Z=<z_1, z_2, \dots, z_k>$ a greatest common subsequence(GCS) of $X$ and $Y$.Then: If $x_m=y_n$,then $z_k=x_m=y_n$ and $Z_{k-1}$ is a GCS of $X_{m-1}$ and $Y_{n-1}$. If $x_m \neq y_n$ and $z_k...
  19. M

    MHB Show that the sequence has a decreasing subsequence

    Hi ! :) Let x_{n} a sequence of positive numbers.How could I show that it has a decreasing subsequence that converges to 0,knowing that inf{ x_{n} ,n ε N} =0??
  20. S

    Proof of subsequence convergence

    prove if ## a_{2k} \rightarrow l ## and ## a_{2k-1} \rightarrow l ## then ## a_n \rightarrow l ## where ## a_{2k} ## and ## a_{2k-1} ## are subsequences of ## a_n ## my attempt: since: ## a_{2k} \rightarrow l ## then ## \forall \epsilon > 0 ## ##\exists N_1 \in \mathbb{R}## s.t. ##2k > N_1...
  21. P

    Finding a subsequence from a sequence that converges

    Homework Statement a real sequence (x_{n}) is defined as follows: we take the elements in order (starting from x0) to be 0, 1 , 0 , 1/10 , 2/10 ,... , 9/10, 1 0 , 1/100 ,2/100 ,..., 99/100 , 1 , 0 , 1/1000,... So we take p for p = 0, 1, then p/10 for p = 0; ... 10, then p=100 for p =...
  22. P

    Finding a convergent subsequence does the sequence need to be bounded

    Homework Statement 2.11. Determine (explicitly) a convergent subsequence of the sequence in R2 given for n = 1; 2; : : : by xn =(e^{n}sin(n\pi/7),((4n+3/3n+4)cos(n\pi/3)) I know that the Bolzano-weierstrass theorem says that every bounded sequence has a convergent subsequence. I...
  23. Fernando Revilla

    MHB Can a sequence without a convergent subsequence have a limit of infinity?

    I quote a question from Yahoo! Answers I have given a link to the topic there so the OP can see my response.
  24. A

    MHB Prove No Uniformly Convergent Subsequence: Functional Sequence

    SOLVED Prove that the functional sequence has no uniformly convergent subsequence -check n \in \mathbb{R}, \ \ f_n \ : \ \mathbb{R} \rightarrow \mathbb{R}, \ \ f_n(x) =\cos nx We want to prove that {f_n} has no uniformly convergent subsequence. This is my attempt at proving that: Suppose...
  25. T

    Subsequence that Sums Up to Half the Total Sum

    Hi all, I was just looking at the U.S. electoral map, and I was wondering if there could possibly be a tie in presidential elections (the answer is probably no). I tried to think of an efficient algorithm to answer this question, but due to my limited intelligence and imagination, all I...
  26. C

    MHB Confirm Answers on Homework Sheet: Subsequence Convergence

    Question from my homework sheet. Can someone confirm I've got these correct. Let (an)n∈N be any sequence of real numbers. Which of the following statements are true? Give precise references to the results in the Lecture Notes for those which are true. Construct counter examples for those that...
  27. P

    Infinite sequences containing every possible subsequence

    Hi, True or False: Every infinite sequence of natural numbers, who's terms are randomly ordered, must contain every possible subsequence of any length, including infinity. For example, does the infinite and random sequence \small M of natural numbers require that the subsequence {59,1,6}...
  28. N

    Longest increasing subsequence

    Problem: "Let x_1, ..., x_n be i.i.d random variables uniformly on [0,1]. Let X be the length of the longest increasing subsequence of x_1, ..., x_n. Show that E[X] \ge (1-o(1))(1-e^{-1}) \sqrt{n}." Hi forum! Using the Erdos' lemma I can only deduce that E[X] \ge \frac{1}{2} \sqrt{n}...
  29. G

    Sequence is convergent if it has a convergent subsequence

    Homework Statement Show that an increasing sequence is convergent if it has a convergent subsequence. The Attempt at a Solution Suppose xjn is a subsequence of xn and xjn→x. Therefore \existsN such that jn>N implies |xjn-x|<\epsilon It follows that n>jn>N implies |xn-x|<\epsilon...
  30. alexmahone

    MHB Subsequence - absolute convergence

    Let $\{a_n\}$ be a sequence, and $\{a_{n_i}\}$ be any subsequence. Prove that if $\sum_{n=0}^\infty a_n$ is absolutely convergent, then $\sum_{i=0}^\infty a_{n_i}$ is absolutely convergent. My attempt: $\sum |\ a_n|$ is convergent. $b_n=\left\{ \begin{array}{rcl}|a_{n_i}|\ &\text{for}& \...
  31. A

    Subsequence of a cauchy sequence in R

    Homework Statement If \{a_{n}\}\in\mathbb{R} is Cauchy, \forall\epsilon>0,\exists a subsequence \{a_{k_{j}}\} so that |a_{k_{j}}-a_{k_{j+1}}|<\frac{\epsilon}{2^{j+1}}. The Attempt at a Solution Since \{a_{k_{j}}\} is Cauchy,\forall\epsilon>0,\exists N_{\epsilon} such that for j,j+1\geq...
  32. S

    Can a bounded subsequence have infinitely many convergent subsequences?

    I'm not sure if I am confusing myself or not, but a friend and I were trying to figure this out. Basically, I know that if a sequence is bounded, we are guaranteed at least one convergent subsequences. However, is it possible for a bounded sequence to have infinitely many of such subsequences?
  33. J

    Prove that a sequence of functions has a convergent subsequence

    Homework Statement Let \{ f_{n} \}_{n=1}^{\infty} \subset C[0,1] be twice differentiable, and satisfying 0 = f_{n}(0) = f'_{n}(0) and \| f''_{n}\|_{\infty } . Prove that \{ f_{n} \}_{n=1}^{\infty} has a convergent subsequence. Homework Equations So since C[0,1] is a compact metric...
  34. B

    Non Decreasing Subsequence in [0,1]

    Not a homework problem. I was reading this analysis book by Korner and in it there was a question about Bolzano-Weierstrass property in \mathbb{R} . it states \text{Find a sequence} \ x_n \in [0,1], \text{such that given any x} \in [0,1], \text{we can find} \ n_1 < n_2 < ... s.t. \ x_n_j...
  35. A

    Does Monotone Convergence imply Convergence Subsequence?

    Homework Statement Results i) if (a_n) tends to L as n tends to infinity, then a_{n_r} tends to L as r tend to infinity ii)if (a_n) tends to infinity as n tends to infinity, then a_{n_r} tends to infinity as r tend to infinity using this result prove that if (a_n) is an increasing...
  36. M

    Tychonoff's theorem and convergent subsequence

    Let X be the countably infinite product of closed unit intervals under the product topology. By Tychonoff's theorem, this space is compact. Consider the sequence \{ x_n \} , where x_k is the vector that is zero for all components except for the kth component, which is 1. Since this space...
  37. M

    Bounded sequence that diverges, convergent subsequence

    Homework Statement Let (sn) be a sequence in R that is bounded but diverges. Show that (sn) has (at least) two convergent subsequences, the limits of which are different. Homework Equations The Attempt at a Solution I know that a convergent subsequence exists by...
  38. K

    Bounded sequence, convergent subsequence

    Homework Statement Asssume (an) is a bounded sequence with the property that every convergent subsequence of (an) converges to the same limit a. Show that (an) must converge to a. Homework Equations The Attempt at a Solution If the subsequence converges to a we have , we have...
  39. W

    How can we determine the limit of a sequence through stochastic convergence?

    Hello all, There is always a confusing question in my mind regarding sequence and subsequence, particularly in the field of probability theory and stochastic integration. Given a sequence H^{n} which converges in probability to H, we know that there exists a subsequence H^{n_{k}} converging...
  40. J

    X is an accumulation point show there is subsequence that converges to x

    Homework Statement Suppose x is an accumulation point of {an: n is a member of integers}. Show there is a subsequence of (an) that converges to x. The Attempt at a Solution I'm a little stuck on this one. I know that since x is an accumulation point then every neighborhood around x...
  41. K

    Cauchy sequence with a convergent subsequence

    Homework Statement Theorem: In a metric space X, if (xn) is a Cauchy sequence with a subsequence (xn_k) such that xn_k -> a, then xn->a. Homework Equations N/A The Attempt at a Solution 1) According to this theorem, if we can show that ONE subsequence of xn converges to a, is that...
  42. K

    Convergence of subsequence in metric space

    Homework Statement Homework Equations N/A The Attempt at a Solution I'm really not having much progress on this question. My thoughts are as shown above.
  43. K

    Show there exists a SUBSEQUENCE converging to L

    Homework Statement Homework Equations N/A The Attempt at a Solution Actually I read over this question for about 10 times already. But, I am not sure how to start. I know that I have to construct a subsequence one term at a time and show that it converges to L. But all the different...
  44. K

    Does every subsequence of a_n converge to a?

    Idea of a "subsequence" I don't fully understand the idea of a "subsequence"... 1) Say we have an infinite sequence {an} = {1,2,3,4,...} Then if we only take {1,2,3} with FINITE number of elements, is it a subsequence of an? 2) If an is an infinite sequence, is an a subsequence of an...
  45. F

    What is the relationship between lim sup and the limit of a subsequence?

    Homework Statement Show that the lim sup of a bounded sequence is a limit of a subsequence. Homework Equations Sequence: Sn Subsequence: Snk The Attempt at a Solution An existent lim sup means that at a large enough N, the subsequence could hug the bottom of the lim sup to within...
  46. H

    Prove the existance of a subsequence such that

    Homework Statement Notation: |a_n| is the absolute value of a_n. (s_n) signifies a sequences; s_n signifies the value of the sequence at a particular n. Problem: Let n, k be arbitrary elements in N. Let (a_n) be a sequence such that lim inf |a_n| = 0. Prove that there is a...
  47. F

    Prove that if x > limsup s_n, then x is not the limit of any subsequence

    Homework Statement Directly from the definition, for a sequence (s_n)_{n \in \mathbb{N}} \subseteq \mathbb{R} prove that if x > \limsup s_n , then x is not the limit of any subsequence of (s_n). (i.e. Do not use the fact that \limsup s_n is the supremum of the set of subsequential limits.)...
  48. N

    What is the intuitive definition of a subsequence?

    In Rudin's "Principles of Mathematical Analysis" he gives the strict definition for a subsequence as follows: Given a subsequence {pn}, consider a sequence {nk}of positive integers, such that n1<n2<n3<... Then the sequence {pni} is called a subsequence of {pn}. If {pni} converges, its limit...
  49. P

    Java Java recursion longest common subsequence

    can someone explain java recursion to me?
  50. P

    Easy convergent subsequence question.

    Homework Statement Consider the sequence {x_k} = {(arctan(k^2+1),sink)} in R^2. Is there a convergent subsequence? Justify your answer. Homework Equations Every bounded sequence in R^n has a convergent subsequence. The Attempt at a Solution To show {x_k} is bounded: The range...
Back
Top