It is super easy to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to $n$-nth element of the sequence $0,1,0,1,0,1,0,1,0,1,0,1,...$

$$X_0 = \left(\begin{array}{c}1\\1\\\end{array}\right)$$ $$F = \left(\begin{array}{c}-1 & 1\\0 & 1\\\end{array}\right)$$ $$H = \left(\begin{array}{c}1 & 0\end{array}\right)$$

Maybe it is a slightly harder challenge to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to the $n$-nth element of the Fibonacci sequence $1,1,2,3,5,8,13,21,34,...$

$$X_0 = \left(\begin{array}{c}0\\1\\\end{array}\right)$$ $$F = \left(\begin{array}{c}0 & 1\\1 & 1\\\end{array}\right)$$ $$H = \left(\begin{array}{c}1 & 0\end{array}\right)$$

No big deal, isn't it?

Then try to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to the $n$-nth element of the sequence $\left(\begin{array}{c}0\\0\\0\\\end{array}\right), \left(\begin{array}{c}0\\0\\1\\\end{array}\right), \left(\begin{array}{c}0\\1\\0\\\end{array}\right), \left(\begin{array}{c}0\\1\\1\\\end{array}\right), \left(\begin{array}{c}1\\0\\0\\\end{array}\right), \left(\begin{array}{c}1\\0\\1\\\end{array}\right), \left(\begin{array}{c}1\\1\\0\\\end{array}\right), \left(\begin{array}{c}1\\1\\1\\\end{array}\right), ...$

This is the sequence of all 3-digit binary numbers; please assume that this series repeats itself forever.

And what if I want to express this way the sequence of all $k$-digit binary numbers? How big does the matrix $F$ need to be? There is a very straightforward solution where F has dimensions $2^k \times 2^k$. Is there a better solution?