A sequence $\{p_n\}$ defined by $p_1=1,\ p_2=1,\ p_{n+2}=p_n+p_{n+1}\ (n\geq 1)$ is called Fibonacci Sequence and the general term is given by 

\[p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}\]

if necessary, use the fact to answer the following questions.

A natural sequence $X_n\ (n=1,\ 2,\ \cdots)$ such that the figure of each digit is $0$ or $1$ is determined by the following rules.

(i) $X_1=1$.

(ii) If the figure $\alpha$ in some digit in $X_n$ is $0$, then we replace $\alpha$ into $1$ and if $\alpha$ is $1$, then we replace $\alpha$ into $'10'$. Denote $X_{n+1}$ natural number which can be obtained by replacing such this for each digit. For instance, $X_1=1,\ X_2=10,\ X_3=101,\ X_4=10110,\ X_5=10110101,\ \cdots$.

(1) Find the number $a_n$ of the digit of $X_n$.

(2) Find the number $b_n$ of appearing the arrangement of $'01'$ in $X_n$, for instance $b_1=0,\ b_2=0,\ b_3=1,\ b_4=1,\ b_5=3,\ \cdots$.

[i]1992 Tokyo University entramce exam/Humanities[/i]
### Part (1): Finding the number of digits \(a_n\) in \(X_n\)

1. **Define the sequence and initial conditions:**
   - Given \(X_1 = 1\), we see that \(X_1\) has 1 digit.
   - For \(X_2\), replacing 1 with '10', we get \(X_2 = 10\), which has 2 digits.
   - For \(X_3\), replacing 1 with '10' and 0 with '1', we get \(X_3 = 101\), which has 3 digits.
   - For \(X_4\), replacing 1 with '10' and 0 with '1', we get \(X_4 = 10110\), which has 5 digits.

2. **Establish the recurrence relation:**
   - Let \(0_n\) and \(1_n\) be the number of 0's and 1's in \(X_n\), respectively.
   - Each 0 in \(X_n\) contributes a 1 to \(X_{n+1}\).
   - Each 1 in \(X_n\) contributes '10' to \(X_{n+1}\), adding one 1 and one 0.
   - Therefore, \(0_{n+1} = 1_n\) and \(1_{n+1} = 0_n + 1_n\).

3. **Relate the number of digits to the Fibonacci sequence:**
   - The total number of digits in \(X_n\) is \(0_n + 1_n\).
   - From the recurrence relations, we have \(1_{n+1} = 0_n + 1_n\) and \(0_{n+1} = 1_n\).
   - This implies \(1_{n+1} = 1_n + 1_{n-1}\), which is the Fibonacci sequence.
   - Given \(1_1 = 1\) and \(1_2 = 1\), we see that \(1_n = p_n\), where \(p_n\) is the \(n\)-th Fibonacci number.

4. **Determine the number of digits:**
   - The number of digits in \(X_n\) is \(1_n + 0_n = p_n + p_{n-1} = p_{n+1}\).

### Part (2): Finding the number of occurrences \(b_n\) of the arrangement '01' in \(X_n\)

1. **Prove the concatenation property:**
   - We need to show that \(X_{n+1} = \overline{X_n X_{n-1}}\).
   - Base cases: \(X_1 = 1\), \(X_2 = 10\), \(X_3 = 101\), \(X_4 = 10110\), etc.
   - Assume \(X_k = \overline{X_{k-1} X_{k-2}}\) for \(k < n\).
   - By the replacement rules, \(C(\overline{a_1 a_2}) = \overline{C(a_1) C(a_2)}\).
   - Therefore, \(X_{n+1} = C(X_n) = C(\overline{X_{n-1} X_{n-2}}) = \overline{C(X_{n-1}) C(X_{n-2})} = \overline{X_n X_{n-1}}\).

2. **Count the occurrences of '01':**
   - A '01' can be formed if there is a '01' in \(X_n\) or \(X_{n-1}\).
   - Additionally, if the last digit of \(X_n\) is 0, the first digit of \(X_{n-1}\) is always 1, forming another '01'.
   - The last digit of \(X_n\) is 0 if \(n\) is even.

3. **Formulate the recurrence relation for \(b_n\):**
   - \(b_{n+1} = b_n + b_{n-1} + \frac{1 + (-1)^{n+1}}{2}\).

4. **Solve the recurrence relation:**
   - Let \(a_n = b_n + \frac{1 + (-1)^{n+1}}{2}\).
   - Then \(a_{n+1} = a_n + a_{n-1}\), with initial conditions \(a_1 = 0\) and \(a_2 = 1\).
   - Thus, \(a_n = p_{n-1}\).

5. **Express \(b_n\) in terms of Fibonacci numbers:**
   - \(b_n = p_{n-1} - \frac{1 + (-1)^{n+1}}{2}\).

The final answer is \( \boxed{ a_n = p_{n+1} } \) and \(b_n = p_{n-1} + \frac{(-1)^n - 1}{2}\).