Prove that the set of all periodic sequences (from some index) of natural numbers is countable

Question

This exercise is from my course textbook and comes with a bunch of other exercises which practice the theorem that countable union of countable sets is countable.

So I started by notating for every $k\in \mathbb{N}$ the set $X_k$ as the set of all periodic sequences from the index $k$ of natural numbers. now, $X=\displaystyle{\bigcup_{k\in \mathbb{N}}{X_k}}$ so it's only left to prove that for each $k\in \mathbb{N}$ the set $X_k$ is countable but I can't find an injection from $X_k$ to a countable set.

Answer 1

Hint: Set $X_k^n$ to be the set of integer sequences that have period $k$, starting at index $n$. Now observe that $X = \bigcup \limits_{(k, n) \in \mathbb{N}^2} X_k^n$.

Answer 2

For $k \ge 1$, call $U_k = \{ \mbox{sequences } (x_n)_n \in X : \max_n x_n =k-1 \}$. Clearly $$X= \bigcup_k U_k$$ so it is enough to show that $U_k$ is countable. Clearly $U_1$ has only one element : the constant $0$ sequence.

For $k \ge 2$, do as follows: inject $U_k \longrightarrow \Bbb{Q}$ with the map $$(x_n)_n \mapsto \sum_{n=0}^{\infty} x_n (k+1)^{-n}$$ i.e. you associate to a periodic sequence its periodic $(k+1)$-nary number, which is rational.

Maybe the most natural choice would have been $(x_n)_n \mapsto \sum_{n=0}^{\infty} x_n k^{-n}$. But the problem is that $k$-nary representation of rational numbers is not unique (problems arise for example when you have $0.49999999\dots = 0.50000000\dots$). Avoiding the largest cipher, we get uniqueness of representation.

Finally, since $\Bbb{Q}$ is well-known to be countable, you can conlude that $U_k$ is countable.