Define an infinite binary sequence as follows: start with 0 and repeatedly replace each 0 by $001$ and each $1$ by $0$.
Provide, with proof, a formula for the positions of the nth one and a formula for the position of the nth zero.
Note: I've fixed a typo below; originally, it should have said $\lfloor \sqrt{2}n\rfloor$ for the position of the nth zero.
I know the nth one is at $\lfloor (2+\sqrt{2})n\rfloor$ and that the nth zero is at $\lfloor \sqrt{2}n\rfloor$. I also know that if I let $w_1 = 0,$ and for $k\ge 2, w_k$ be the string obtained by replacing every $0$ in $w_{k-1}$ with $001$ and every 1 with a 0, then $w_k$ satisfies the recurrence $w_{k+1} = w_k w_k w_{k-1}$. However, I'm not sure how to show this by induction. It seems complicated to come up with an explicit formula in terms of ones and zeroes for $w_k$, and the inductive hypothesis doesn't seem to provide much help for the inductive step, unless I can formally deduce where the 1's and 0's are. I'm not sure how to prove the formulas for the nth one and nth zero, but I know how one can intuitively obtain them. One does this by determining the limit of $\frac{a_k}{a_{k-1}}$, where $a_k$ is the number of zeroes in $w_k$ and $b_k$ is the number of ones in $w_k$. Note that $a_{k+1} = 2a_k + a_{k-1}$ and $b_k = a_{k-1}$ for $k\ge 1$, where $a_0 = 0$. After one determines the limit, one can guess that the ith one will be in approximately every $\dfrac{1}{\frac{a_k}{a_k + a_{k-1}}}\to (2+\sqrt{2})$th position.
This sequence is the Sturmian word corresponding to $1/\sqrt{2}$. See https://en.wikipedia.org/wiki/Sturmian_word and https://en.wikipedia.org/wiki/Beatty_sequence for a detailed explanation.