Consider a sequence $0, 1, 2, 1, 2,···$. Explain why any sequence ${x_k}$ with the property $x_k =$ $1$ or $ 2$ for each $k$ , is a subsequence of this sequence.
I have tried to use the Bolzano-Weierstrass theorem but I am not sure if it is suitable for this question or not.
Bolzano-Weierstrass cannot help you because the given sequence is not convergent and we are not asked about always non-convergent subsequences.
We start with the sequence $(a_i)_{i=0}^\infty$: \begin{align*} a_0 &= 0 \\ a_i &= \begin{cases} 1 ,& \text{$i$ is odd} \\ 2 ,& \text{$i>0$ is even} \end{cases} \end{align*} and wish to show $(x_k)_{k=1}^\infty$ is a subsequence of $(a_i)$ where $x_k \in \{1,2\}$ for all $k$.
We must find a function $i(k)$ such that $a_{i(k)} = x_k$ for all $k \in [1,\infty)$. Set $i(1) = x_1$. For all $k > 1$, set $$ \Delta i(k) = \begin{cases} 1 ,& x_{k+1} \neq x_k \\ 2 ,& x_{k+1} = x_k \end{cases} \text{.} $$ and then $i(k) = i(k-1) + \Delta i(k)$.
Now we proceed by induction. First, $$ x_1 = a_{i(1)} = a_{x(1)} = \begin{cases} 1 ,& x_1 = 1 \\ 2 ,& x_1 = 2 \end{cases} \text{.} $$ Now suppose $a_{i(k-1} = x_{k-1}$. Then \begin{align*} a_{i(k)} &= a_{i(k-1) + \Delta i(k)} \\ &= a_{i(k-1) + \begin{cases} 1 ,& x_{k} \neq x_{k-1} \\ 2 ,& x_{k} = x_{k-1} \end{cases} } \\ &= a_{\begin{cases} i(k-1) + 1 ,& x_{k} \neq x_{k-1} \\ i(k-1) + 2 ,& x_{k} = x_{k-1} \end{cases} } \\ &= \begin{cases} a_{i(k-1) + 1} ,& x_{k} \neq x_{k-1} \\ a_{i(k-1) + 2} ,& x_{k} = x_{k-1} \end{cases} \\ &= \begin{cases} a_{i(k-1) + 1} ,& x_{k} \neq x_{k-1} \\ a_{i(k-1)} ,& x_{k} = x_{k-1} \end{cases} \text{,} \end{align*} where the last equality uses that adding two to an even number yields an even number and likewise for an odd number. But we are done. If $x_{k} = x_{k-1}$, we have proven $a_{i(k)} = a_{i(k-1)}$, as needed, and if $x_k \neq x_{k-1}$ we switch $a_{i(k)}$ between the even index and odd index subsequences of $a_i$ so we switch $a_{i(k)}$ between $1$ and $2$ precisely when $x_k$ switches. Therefore, we have shown that $(x_k)$ is a subsequence of $(a_i)$.
The question asks to explain this so I'm going to stick with an informal explanation (see the other answer for a more formal proof). Given any sequence of $1$'s and $2$'s let's see how we would go about to extract this as a subsequence of $a_k = \{0,1,2,1,2,1,2,\ldots\}$ (a subsequence is defined as a sequence on the form $\{a_{i_k}\}_{k=1}^\infty$ where $i_k$ is an increasing sequence of integers).
Lets explain the method with a sequence that starts off like $x_k = \color{red}{2},\color{blue}{2},\color{green}{1},\ldots$. We start with the first element $x_1 = \color{red}{2}$. We now scan $a_k$ from the beginning until we find a $2$. The index this corresponds to is $i_1 = 3$: $$a_k = \{0,1,\color{red}{2},1,2,1,2,\ldots\}$$
Next number is $x_2 = \color{blue}{2}$. We start from $k=i_1+1 = 4$ and scan forward till we find another $2$. The index this corresponds to is seen to be $i_2 = 5$: $$a_k = \{0,1,\color{red}{2},1,\color{blue}{2},1,2,\ldots\}$$ Next number is $x_3 = \color{green}{1}$. We starts from $k = i_2+1=6$ and scan forward till we find a $1$. The index this corresponds to is seen to be $i_3 = 6$: $$a_k = \{0,1,\color{red}{2},1,\color{blue}{2},\color{green}{1},2,\ldots\}$$ We continue this procedure to generate the sequence $i_k = \{3,5,6,\ldots\}$ which will have the property, by construction, that $a_{i_k} = x_k$.
This is a simple method to generate the desired subsequence. Now we need to show that it will always work. What might go wrong is that at some point there are not more $1$'s or $2$'s left in the sequence so our search will never find a match. This will never happen here. If the last number we picked was a $1$ then the next two numbers in $a_k$ is $2,1$ and likewise if the last number we picked was a $2$ then the next two numbers in $a_k$ is $1,2$ so no matter what number we have next in $x_k$ it will always be found to the right of the previous element we picked in $a_k$.
To see if you understand it try to show that the specific form of $a_k$ is of no importance here and that all we need for this method to always work is that it has infinite numbers of $1$'s and $2$'s. Also try to convince yourself that you can construct an infinite number of different subsequences (different choices for the $i_k$'s) that matches $x_k$.
