IMO Problem Shortlist

For a binary word $w={\sigma }_1\dots {\sigma }_n$ of length $n$ and a letter $\sigma \in \{0,1\}$ let $w\sigma ={\sigma }_1\dots {\sigma }_n\sigma$ and $\sigma w=\sigma {\sigma }_1\dots {\sigma }_n$. Moreover let $\bar{w}={\sigma }_n\dots {\sigma }_1$ and let $\varnothing$ be the empty word (of length 0 and with $\bar{\varnothing }=\varnothing$ ). 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{array}{c}(u,v{)}^{\varnothing }=v,(u,v{)}^0=2u+3v,(u,v{)}^1=3u+v\\ (u,v{)}^{w\sigma \epsilon }=\{\begin{array}{ll}2(u,v{)}^w+3(u,v{)}^{w\sigma },& \text{ if }\epsilon =0\\ 3(u,v{)}^w+(u,v{)}^{w\sigma },& \text{ if }\epsilon =1\end{array}\end{array}$$ 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{array}{c}{\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\end{array}\text{\hspace{1em}(1)}$$ and that for $\epsilon \in \{0,1\}$ $$\begin{array}{c}(u,v{)}^{\epsilon w}={\left(v,(u,v{)}^{\epsilon }\right)}^w\end{array}\text{\hspace{1em}(2)}$$ Obviously, for $n\ge 1$ and $w={\epsilon }_1\dots {\epsilon }_{n-1}$, we have $a_n=(1,7{)}^w$ and $b_n=(1,7{)}^{\bar{w}}$. Thus it is sufficient to prove that $$\begin{array}{c}(1,7{)}^w=(1,7{)}^{\bar{w}}\end{array}\text{\hspace{1em}(3)}$$ 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 \epsilon$ be a binary word of length $n\ge 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{)}^{\varnothing }$ for $\sigma \in \{0,1\},(1,7{)}^0=23$, and $(1,7{)}^1=10$.

First let $\epsilon =0$. Then in view of the induction hypothesis and the equalities (1) and (2), we obtain $$\begin{array}{rl}(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{array}$$ Now let $\epsilon =1$. Analogously, we obtain $$\begin{array}{rl}(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{array}$$ Thus the induction step is complete, (3) and hence also $a_n=b_n$ are proved.