Can you find two sequences $(a_{n})_{n=0}^{\infty}$ and $(b_{n})_{n=0}^{\infty}$ which are not the same sequence, but such that each is a subsequence of the other?
My solution
I have thought about $a_{n} = (-1)^{n}$ and $b_{n} = (-1)^{n+1}$, but I would like to know if there are more interesting examples.
Can someone suggest another example?
On
The problem is equivalent to asking for a sequence that is a proper subsequence of itself. Here’s an explicit example that doesn’t result simply from a shift.
Let $\pi:\Bbb N\times\Bbb N\to\Bbb N$ be the Cantor pairing function; it’s a bijection, so there are functions $\sigma_1,\sigma_2:\Bbb N\to\Bbb N$ such that $\pi^{-1}(n)=\langle\sigma_1(n),\sigma_2(n)\rangle$ for each $n\in\Bbb N$. For $n\in\Bbb N$ let $a_n=\sigma_1(n)$; then the sequence $\langle a_n:n\in\Bbb N\rangle$ is a proper subsequence of itself.
Recursively construct a function $\varphi:\Bbb N\to\Bbb N$ such that
$$\varphi(n)=\min\left\{k\in\Bbb N:k>n\text{ and }k>\max_{\ell<n}\varphi(\ell)\text{ and }\sigma_1(k)=\sigma_1(n)\right\}\;;$$
This is possible because
$$\{k\in\Bbb N:\sigma_1(k)=\sigma_1(n)\}=\{\pi(\langle\sigma_1(n),\ell\rangle):\ell\in\Bbb N\}$$
is infinite and therefore contains arbitrarily large natural numbers.
Then $\varphi$ is strictly increasing, so $\langle a_{\varphi(n)}:n\in\Bbb N\rangle$ is a subsequence of $\langle a_n:n\in\Bbb N\rangle$. Moreover, $\varphi(n)>n$ for each $n\in\Bbb N$, so $\langle a_{\varphi(n)}:n\in\Bbb N\rangle$ is a proper subsequence of $\langle a_n:n\in\Bbb N\rangle$. Finally, by construction $a_{\varphi(n)}=\sigma_1(\varphi(n))=\sigma_1(n)=a_n$ for each $n\in\Bbb N$.
Note that the underlying idea is exactly the same as in Ross Millikan’s example.
You can take both sequences to be randomly $0$ and $1$. As long as both have an infinite number of $0$s and an infinite number of $1$s, which happens with probability $1$, each will be a subsequence of the other. For example, if $a=011000101010\ldots$ we just look for the first $0$ in $b$, then the next $1$ after the first $0$, then the next $1$ after that and so on. We will never run out of either one, so $a$ is a subsequence of $b$. We can use the same process to show $b$ is a subsequence of $a$.