MathDB

Let

n

be a positive integer. Given a sequence

\varepsilon_1

\dots

\varepsilon_{n - 1}

with

\varepsilon_i = 0

\varepsilon_i = 1

for each

i = 1

\dots

n - 1

, the sequences

a_0

\dots

a_n

and

b_0

\dots

b_n

are constructed by the following rules: a_0 = b_0 = 1, a_1 = b_1 = 7, \begin{array}{lll} a_{i+1} = \begin{cases} 2a_{i-1} + 3a_i, \\ 3a_{i-1} + a_i, \end{cases} & \begin{array}{l} \text{if } \varepsilon_i = 0, \\ \text{if } \varepsilon_i = 1, \end{array} & \text{for each } i = 1, \dots, n - 1, \$$15pt] b_{i+1}= \begin{cases} 2b_{i-1} + 3b_i, \\ 3b_{i-1} + b_i, \end{cases} & \begin{array}{l} \text{if } \varepsilon_{n-i} = 0, \\ \text{if } \varepsilon_{n-i} = 1, \end{array} & \text{for each } i = 1, \dots, n - 1. \end{array} Prove that

a_n = b_n

.
Proposed by Ilya Bogdanov, Russia

Problem Statement