ISL 2009 C3

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, 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} \text { for each } i=1, \ldots, n-1,\right. \\ 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} \text { for each } i=1, \ldots, n-1 .\right. \end{gathered}$$ Prove that $a_{n}=b_{n}$.