Problem 1915

For a binary word $w=\sigma_{1} \ldots \sigma_{n}$ of length $n$ and a letter $\sigma \in\{0,1\}$ let $w \sigma= \sigma_{1} \ldots \sigma_{n} \sigma$ and $\sigma w=\sigma \sigma_{1} \ldots \sigma_{n}$. Moreover let $\bar{w}=\sigma_{n} \ldots \sigma_{1}$ and let $\emptyset$ be the empty word (of length 0 and with $\bar{\emptyset}=\emptyset$ ). Let $( u, v )$ be a pair of two real numbers. For binary words $w$ we define recursively the numbers $(u, v)^{w}$ as follows:
$$\begin{gathered} (u, v)^{\emptyset}=v, \quad(u, v)^{0}=2 u+3 v, \quad(u, v)^{1}=3 u+v \\ (u, v)^{w \sigma \varepsilon}= \begin{cases}2(u, v)^{w}+3(u, v)^{w \sigma}, & \text{ if } \varepsilon=0 \\ 3(u, v)^{w}+(u, v)^{w \sigma}, & \text{ if } \varepsilon=1\end{cases} \end{gathered}$$
It easily follows by induction on the length of $w$ that for all real numbers $u_{1}, v_{1}, u_{2}, v_{2}, \lambda_{1}$ and $\lambda_{2}$
$$\begin{equation*} \left(\lambda_{1} u_{1}+\lambda_{2} u_{2}, \lambda_{1} v_{1}+\lambda_{2} v_{2}\right)^{w}=\lambda_{1}\left(u_{1}, v_{1}\right)^{w}+\lambda_{2}\left(u_{2}, v_{2}\right)^{w} \tag{1} \end{equation*}$$
and that for $\varepsilon \in\{0,1\}$
$$\begin{equation*} (u, v)^{\varepsilon w}=\left(v,(u, v)^{\varepsilon}\right)^{w} \tag{2} \end{equation*}$$
Obviously, for $n \geq 1$ and $w=\varepsilon_{1} \ldots \varepsilon_{n-1}$, we have $a_{n}=(1,7)^{w}$ and $b_{n}=(1,7)^{\bar{w}}$. Thus it is sufficient to prove that
$$\begin{equation*} (1,7)^{w}=(1,7)^{\bar{w}} \tag{3} \end{equation*}$$
for each binary word $w$. We proceed by induction on the length of $w$. The assertion is obvious if $w$ has length 0 or 1. Now let $w \sigma \varepsilon$ be a binary word of length $n \geq 2$ and suppose that the assertion is true for all binary words of length at most $n-1$.
Note that $(2,1)^{\sigma}=7=(1,7)^{\emptyset}$ for $\sigma \in\{0,1\}, (1,7)^{0}=23$, and $(1,7)^{1}=10$.

First let $\varepsilon=0$. Then in view of the induction hypothesis and the equalities (1) and (2), we obtain
$$\begin{aligned} (1,7)^{w \sigma 0}&=2(1,7)^{w}+3(1,7)^{w \sigma}=2(1,7)^{\bar{w}}+3(1,7)^{\sigma \bar{w}}=2(2,1)^{\sigma \bar{w}}+3(1,7)^{\sigma \bar{w}} \\ &=(7,23)^{\sigma \bar{w}}=(1,7)^{0 \sigma \bar{w}} \end{aligned}$$
Now let $\varepsilon=1$. Analogously, we obtain
$$\begin{aligned} (1,7)^{w \sigma 1}&=3(1,7)^{w}+(1,7)^{w \sigma}=3(1,7)^{\bar{w}}+(1,7)^{\sigma \bar{w}}=3(2,1)^{\sigma \bar{w}}+(1,7)^{\sigma \bar{w}} \\ &=(7,10)^{\sigma \bar{w}}=(1,7)^{1 \sigma \bar{w}} \end{aligned}$$
Thus the induction step is complete, (3) and hence also $a_{n}=b_{n}$ are proved.