Question 23
Let $n$ be a positive integer. Given a sequence $\varepsilon_{1}, \ldots, \varepsilon_{n-1}$ with $\varepsilon_{i}=0$ or $\varepsilon_{i}=1$ for each $i=1, \ldots, n-1$, the sequences $a_{0}, \ldots, a_{n}$ and $b_{0}, \ldots, b_{n}$ are constructed by the following rules:
$$
\begin{gathered}
a_{0}=b_{0}=1, \quad a_{1}=b_{1}=7 \\
a_{i+1}=\left\{\begin{array}{ll}
2 a_{i-1}+3 a_{i}, & \text{ if } \varepsilon_{i}=0, \\
3 a_{i-1}+a_{i}, & \text{ if } \varepsilon_{i}=1,
\end{array}\right. \quad \text{ for each } i=1, \ldots, n-1, \\
b_{i+1}=\left\{\begin{array}{ll}
2 b_{i-1}+3 b_{i}, & \text{ if } \varepsilon_{n-i}=0, \\
3 b_{i-1}+b_{i}, & \text{ if } \varepsilon_{n-i}=1,
\end{array}\right. \text{ for each } i=1, \ldots, n-1
\end{gathered}
$$
Prove that $a_{n}=b_{n}$.
$$
\begin{gathered}
a_{0}=b_{0}=1, \quad a_{1}=b_{1}=7 \\
a_{i+1}=\left\{\begin{array}{ll}
2 a_{i-1}+3 a_{i}, & \text{ if } \varepsilon_{i}=0, \\
3 a_{i-1}+a_{i}, & \text{ if } \varepsilon_{i}=1,
\end{array}\right. \quad \text{ for each } i=1, \ldots, n-1, \\
b_{i+1}=\left\{\begin{array}{ll}
2 b_{i-1}+3 b_{i}, & \text{ if } \varepsilon_{n-i}=0, \\
3 b_{i-1}+b_{i}, & \text{ if } \varepsilon_{n-i}=1,
\end{array}\right. \text{ for each } i=1, \ldots, n-1
\end{gathered}
$$
Prove that $a_{n}=b_{n}$.