TITLE: What fraction of the terms of $S_{64}$ are odd?
QUESTION [1 upvotes]: Let $S_1$ denote the sequence $(1,1)$.
For $n\ge 1$, we build a sequence $S_{n+1}$ by copying sequence $S_n$, inserting blanks between consecutive terms, and filling each blank with the sum of the two terms it's between. Thus we have
\begin{align*}
S_2 &= (1,\underline{2},1),\\
S_3 &= (1,\underline{3},2,\underline{3},1),\\
S_4 &= (1,\underline{4},3,\underline{5},2,\underline{5},3,\underline{4},1),
\end{align*}
and so on.
What fraction of the terms of $S_{64}$ are odd?
I haven't figured out any 1-1 correspondence, and I'm stuck.  Answers are greatly appreciated.

REPLY [2 votes]: Since you only need to know parities (rather than actual values), it is easier to work modulo $2$. The first few sequences modulo $2$ are
1 1
1 0 1
1 1 0 1 1
1 0 1 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1

and you may observe a peculiar pattern of repeating 1 0 1 subsequences.
Use induction to prove that even-numbered sequences are indeed repetitions of 1 0 1, and conclude that the answer is $\frac{2}{3}$.

REPLY [2 votes]: HINT: If $|S_k|$ is the length of $S_k$, then $|S_{k+1}|=2|S_k|-1$, since we add one character for each of the $|S_k|-1$ gaps between adjacent characters of $S_k$. There are many ways to solve this recurrence, and if you’re comfortable with one of them, you can use it here. Alternatively, a quick look at a few values strongly suggests that $|S_k|=2^{k-1}+1$:
$$\begin{array}{rcc}
k:&1&2&3&4&5&6&7\\
|S_k|:&2&3&5&9&17&33&65
\end{array}$$
And indeed this is easily proved by induction on $k$.
It’s not too hard to show by induction that if $S_k=(101)^n$ for some $n$ (where $(101)^n$ means the concatenation of $n$ copies of $101$), then $S_{k+1}=1(101)^{2n-1}1$, and if $S_k=1(101)^n1$, then $S_{k+1}=(101)^{2n+1}$. $S_2=(101)^1$, so $S_k$ has the form $(101)^n$ when $k$ is even and the form $1(101)^n1$ when $k$ is odd. Note that if $S_k=(101)^n$ or $S_k=1(101)^n1$, $n$ is the number of zeroes in $S_k$. 
In particular, $S_{64}$ is of the form $(101)^n$. We also know that $|S_{64}|=2^{63}+1$. From here it’s straightforward to solve for $n$ to get $|S_{64}|_0$ and take the ratio 
$$\frac{|S_{64}|_0}{|S_{64}|}\;.$$
{"set_name": "stack_exchange", "score": 1, "question_id": 1934642}