Is there something wrong with the statement? Right now we trivially have $a_m = b_m$ for all $m$. Edit: and now it's fixed.

The recurrence for $b_{n+1}$ should have $\epsilon_{n-i}$ equal 0 or 1 as the cases, as opposed to $\epsilon_i$.

nsato wrote: ... \[b_{i + 1} = \left\{ \begin{array}{cl} 2b_{i - 1} + 3b_i, & \text{if} \ \epsilon_i = 0, \\ 3b_{i - 1} + b_i, & \text{if} \ \epsilon_i = 1, \end{array} \right.\] for each $i = 1$, $\dots$, $n - 1$... It should be Quote: \[b_{i + 1} = \left\{ \begin{array}{cl} 2b_{i - 1} + 3b_{i}, & \text{if} \ \epsilon_{n-i} = 0, \\ 3b_{i - 1} + b_{i}, & \text{if} \ \epsilon_{n-i} = 1, \end{array} \right.\] for each $i = 1$, $\dots$, $n - 1$.

This is definitely NOT a combinatorial problem. In contrast, it is one of the most algebraic problems on this shortlist. In this post, I give a solution using matrices (only elementary properties of matrices required) and some (less elementary) motivation for it. Part 1: An algebraist's solution: Solution. According to standard notations from linear algebra, we denote by $\mathrm{M}_2\left(\mathbb Q\right)$ the ring of $2\times 2$ matrices over the rational numbers. Define two matrices $A\in \mathrm{M}_2\left(\mathbb Q\right)$ and $B\in \mathrm{M}_2\left(\mathbb Q\right)$ by $A=\left(\begin{array}{cc} 3&2\\ 1&0\end{array}\right)$ and $B=\left(\begin{array}{cc} 1&3\\ 1&0\end{array}\right)$. For every $i\in\left\{1,2,...,n-1\right\}$, define a matrix $K_i\in \mathrm{M}_2\left(\mathbb Q\right)$ by $K_i=\varepsilon_i B + \left(1-\varepsilon_i\right) A$. This clearly yields that $K_i=A$ if $\varepsilon_i=0$, and that $K_i=B$ if $\varepsilon_i=1$. For every $i\in\left\{1,2,...,n-1\right\}$, we have $\left(\begin{array}{c} a_{i+1}\\ a_i\end{array}\right) = K_i \left(\begin{array}{c} a_{i}\\ a_{i-1}\end{array}\right)$ (this is just another way to rewrite the equation $a_{i+1}=\left\{\begin{array}{cl}2a_{i-1}+3a_{i}, &\text{if}\ \epsilon_{i}= 0,\\ 3a_{i-1}+a_{i}, &\text{if}\ \epsilon_{i}= 1,\end{array}\right.$, as the reader can easily check). This yields that every $j\in\left\{0,1,...,n-1\right\}$ satifies $\left(\begin{array}{c} a_{j+1}\\ a_j\end{array}\right) = K_jK_{j-1}...K_1\left(\begin{array}{c} 7\\ 1\end{array}\right)$ (this follows by induction over $j$, using $\left(\begin{array}{c} a_1\\ a_0\end{array}\right)=\left(\begin{array}{c} 7\\ 1\end{array}\right)$). Applying this to $j=n-1$, we obtain $\left(\begin{array}{c} a_{n}\\ a_{n-1}\end{array}\right) =K_{n-1}K_{n-2}...K_1\left(\begin{array}{c} 7\\ 1\end{array}\right)$. Thus, $a_n=\left(\begin{array}{cc} 1&0 \end{array}\right) K_{n-1}K_{n-2}...K_1\left(\begin{array}{c} 7\\ 1\end{array}\right)$ (because $a_n=\left(\begin{array}{cc} 1&0 \end{array}\right)\left(\begin{array}{c} a_{n}\\ a_{n-1}\end{array}\right)$). Similarly, for every $i\in\left\{1,2,...,n-1\right\}$, we have $\left(\begin{array}{c} a_{i+1}\\ a_i\end{array}\right) = K_{n-i} \left(\begin{array}{c} a_{i}\\ a_{i-1}\end{array}\right)$ (this is just another way to rewrite the equation $b_{i+1}=\left\{\begin{array}{cl}2b_{i-1}+3b_{i}, &\text{if}\ \epsilon_{n-i}= 0,\\ 3b_{i-1}+b_{i}, &\text{if}\ \epsilon_{n-i}= 1,\end{array}\right.$, as the reader can easily check). This yields that every $j\in\left\{0,1,...,n-1\right\}$ satifies $\left(\begin{array}{c} b_{j+1}\\ b_j\end{array}\right) = K_{n-j}K_{n-\left(j-1\right)}...K_{n-1}\left(\begin{array}{c} 7\\ 1\end{array}\right)$ (this follows by induction over $j$, using $\left(\begin{array}{c} b_1\\ b_0\end{array}\right)=\left(\begin{array}{c} 7\\ 1\end{array}\right)$). Applying this to $j=n-1$, we obtain $\left(\begin{array}{c} b_{n}\\ b_{n-1}\end{array}\right) = K_1K_2...K_{n-1}\left(\begin{array}{c} 7\\ 1\end{array}\right)$. Thus, $b_n=\left(\begin{array}{cc} 1&0 \end{array}\right) K_1K_2...K_{n-1}\left(\begin{array}{c} 7\\ 1\end{array}\right)$ (because $b_n=\left(\begin{array}{cc} 1&0 \end{array}\right)\left(\begin{array}{c} b_{n}\\ b_{n-1}\end{array}\right)$). So far we have just translated the problem into the language of matrices. Now what is this of use for? We have to prove $a_n=b_n$. Since $a_n=\left(\begin{array}{cc} 1&0 \end{array}\right) K_{n-1}K_{n-2}...K_1\left(\begin{array}{c} 7\\ 1\end{array}\right)$ and $b_n=\left(\begin{array}{cc} 1&0 \end{array}\right) K_1K_2...K_{n-1}\left(\begin{array}{c} 7\\ 1\end{array}\right)$, this means that we have to prove that $\left(\begin{array}{cc} 1&0 \end{array}\right) K_{n-1}K_{n-2}...K_1\left(\begin{array}{c} 7\\ 1\end{array}\right) = \left(\begin{array}{cc} 1&0 \end{array}\right) K_1K_2...K_{n-1}\left(\begin{array}{c} 7\\ 1\end{array}\right)$. In order to do this, it is clearly enough to define some map $s : \mathrm{M}_2\left(\mathbb Q\right) \to \mathrm{M}_2\left(\mathbb Q\right)$ which satisfies $s\left(K_{n-1}K_{n-2}...K_1\right) = K_1K_2...K_{n-1}$, and to show that every matrix $P\in \mathrm{M}_2\left(\mathbb Q\right)$ satisfies $\left(\begin{array}{cc} 1&0 \end{array}\right) P\left(\begin{array}{c} 7\\ 1\end{array}\right) = \left(\begin{array}{cc} 1&0 \end{array}\right) s\left(P\right)\left(\begin{array}{c} 7\\ 1\end{array}\right)$. How do we define such a map? Let $U$ be the invertible matrix $\left(\begin{array}{cc} 7&1\\ 1&2\end{array}\right) \in \mathrm{M}_2\left(\mathbb Q\right)$. Let $s : \mathrm{M}_2\left(\mathbb Q\right) \to \mathrm{M}_2\left(\mathbb Q\right)$ be the map defined by ($s\left(P\right) = UP^TU^{-1}$ for every $P\in\mathrm{M}_2\left(\mathbb Q\right)$). We claim that (1) this map $s$ satisfies $s\left(K_{n-1}K_{n-2}...K_1\right) = K_1K_2...K_{n-1}$, and that (2) this map $s$ satisfies $\left(\begin{array}{cc} 1&0 \end{array}\right) P\left(\begin{array}{c} 7\\ 1\end{array}\right) = \left(\begin{array}{cc} 1&0 \end{array}\right) s\left(P\right)\left(\begin{array}{c} 7\\ 1\end{array}\right)$ for every matrix $P\in \mathrm{M}_2\left(\mathbb Q\right)$. Our definition of $s$ was seemingly a wild guess (I'll explain the motivation behind this guess in Parts 2 and 3), but if we manage to prove that this map $s$ satisfies (1) and (2), then the problem will be solved. Verifying (2) is straightforward computation, which we leave out. Let us now prove (1): The map $s$ satisfies $s\left(I_2\right)=I_2$ (where $I_2$ is the identity matrix $\left(\begin{array}{cc} 1&0\\ 0&1\end{array}\right) \in \mathrm{M}_2$) and $s\left(XY\right)=s\left(Y\right)\cdot s\left(X\right)$ for any two $2\times 2$ matrices $X$ and $Y$. Hence, by induction, we see that the map $s$ satisfies $s\left(X_kX_{k-1}...X_1\right) = s\left(X_1\right) s\left(X_2\right) ... s\left(X_k\right)$ for any $k\in \mathbb N$ and any $2\times 2$ matrices $X_1$, $X_2$, ..., $X_k$. Applying this to $k=n-1$ and $A_i=K_i$, we obtain $s\left(K_{n-1}K_{n-2}...K_1\right) = s\left(K_1\right) s\left(K_2\right) ... s\left(K_{n-1}\right)$. But our goal is to show that $s\left(K_{n-1}K_{n-2}...K_1\right) = K_1K_2...K_{n-1}$. So we must prove that $s\left(K_1\right) s\left(K_2\right) ... s\left(K_{n-1}\right) = K_1K_2...K_{n-1}$ now. Clearly, this will follow immediately once we have shown that $s\left(K_i\right) = K_i$ for every $i\in\left\{1,2,...,n-1\right\}$. But this is simple: Computation shows that $s\left(A\right)=A$ and $s\left(B\right)=B$, and recalling that $K_i=\varepsilon_i B + \left(1-\varepsilon_i\right) A$, we notice that $s\left(K_i\right)=s\left(\varepsilon_i B + \left(1-\varepsilon_i\right) A\right)=\varepsilon_i \underbrace{s\left(B\right)}_{=B} + \left(1-\varepsilon_i\right)\underbrace{s\left(A\right)}_{=A}$ (since $s$ is linear) $=\varepsilon_i B + \left(1-\varepsilon_i\right) A = K_i$. This completes the solution. Part 2: Motivation: Remark: The above solution followed a rather standard procedure (translating linear recurrences into matrix multiplication - this is the same trick that solves many problems about Fibonacci numbers) until the point where we "guessed" the matrix $U$ and the map $s$. How did we do that? The motivation is the following: We need a map $s$ which satisfies (1) and (2). We forget about (2) for a moment, and try to satisfy (1) only. The easiest way to ensure that (1) holds for every choice of $n$ and $\varepsilon_1,\varepsilon_2,...,\varepsilon_{n-1}$ is to choose $s$ as a linear map satisfying $s\left(A\right)=A$ and $s\left(B\right)=B$ (this immediately guarantees that $s\left(K_i\right) = K_i$ for every $i$, because $K_i=\varepsilon_i B + \left(1-\varepsilon_i\right) A $ is a linear combination of $A$ and $B$) and satisfying $s\left(X_kX_{k-1}...X_1\right) = s\left(X_1\right) s\left(X_2\right) ... s\left(X_k\right)$ for any $k\in \mathbb N$ and any $2\times 2$ matrices $X_1$, $X_2$, ..., $X_k$. This condition $s\left(X_kX_{k-1}...X_1\right) = s\left(X_1\right) s\left(X_2\right) ... s\left(X_k\right)$ is fulfilled, for example, when the map $s$ has the form ($s\left(P\right) = UP^TU^{-1}$ for every $P\in\mathrm{M}_2\left(\mathbb Q\right)$) for $U$ an invertible $2\times 2$ matrix. Actually it is fulfilled only in this case, as I explain further below, but as for now let us at least agree that ($s\left(P\right) = UP^TU^{-1}$ for every $P\in\mathrm{M}_2\left(\mathbb Q\right)$) is a good point to start. So now we are searching for a $2\times 2$ matrix $U$ such that the map $s$ defined by ($s\left(P\right) = UP^TU^{-1}$ for every $P\in\mathrm{M}_2\left(\mathbb Q\right)$) satisfies $s\left(A\right)=A$, $s\left(B\right)=B$ and (2). These conditions give linear equations on the entries of this matrix $U$, and the only matrix $U$ which solves all of them is (up to scaling) $\left(\begin{array}{cc} 7&1\\ 1&2\end{array}\right) \in \mathrm{M}_2\left(\mathbb Q\right)$. It is now clear how to proceed from here. Part 3: Further motivation: why our choice of $s$ was not only correct but also the only possible So I promised to tell why the only linear maps $s:\mathrm{M}_2\left(\mathbb Q\right)\to \mathrm{M}_2\left(\mathbb Q\right)$ which satisfy $s\left(X_kX_{k-1}...X_1\right) = s\left(X_1\right) s\left(X_2\right) ... s\left(X_k\right)$ for any $k\in \mathbb N$ and any $2\times 2$ matrices $X_1$, $X_2$, ..., $X_k$ are maps of the form ($s\left(P\right) = UP^TU^{-1}$ for every $P\in\mathrm{M}_2\left(\mathbb Q\right)$) for $U$ an invertible $2\times 2$ matrix. This is a particular case of the following general theorem: Theorem. Let $F$ be a field, and $m$ a positive integer. The only $F$-linear maps $s:\mathrm{M}_m\left(F\right)\to\mathrm{M}_m\left(F\right)$ which satisfy $s\left(X_kX_{k-1}...X_1\right) = s\left(X_1\right) s\left(X_2\right) ... s\left(X_k\right)$ for any $k\in \mathbb N$ and any $m\times m$ matrices $X_1$, $X_2$, ..., $X_k$ (over $F$) are maps of the form ($s\left(P\right) = UP^TU^{-1}$ for every $P\in\mathrm{M}_m\left(F\right)$) for $U$ an invertible $m\times m$ matrix over $F$. Proof of the Theorem. This is going to use some algebra... Let $s$ be a map satisfying $s\left(X_kX_{k-1}...X_1\right) = s\left(X_1\right) s\left(X_2\right) ... s\left(X_k\right)$ for any $k\in \mathbb N$ and any $m\times m$ matrices $X_1$, $X_2$, ..., $X_k$ (over $F$). Define a map $t:\mathrm{M}_m\left(F\right)\to\mathrm{M}_m\left(F\right)$ by ($t\left(P\right)=s\left(P\right)^T$ for every $P\in\mathrm{M}_m\left(F\right)$). Then, this map $t$ satisfies $t\left(X_kX_{k-1}...X_1\right) = t\left(X_1\right) t\left(X_2\right) ... t\left(X_k\right)$ for any $k\in \mathbb N$ and any $m\times m$ matrices $X_1$, $X_2$, ..., $X_k$ (over $F$). In other words, $t$ is an algebra endomorphism of $\mathrm{M}_m\left(F\right)$. Now, a corollary of the Noether-Skolem theorem (Corollary 2.12 in Milne's Class Field Theory) states that all endomorphisms of a central simple $F$-algebra are inner automorphism (note that it usually states this only for automorphisms, but the proof still applies to endomorphisms). Since the matrix algebra $\mathrm{M}_m\left(F\right)$ is central simple, this shows that our endomorphism $t$ is an inner automorphism, i. e., that it has the form ($t\left(P\right) = VPV^{-1}$ for every $P\in\mathrm{M}_m\left(F\right)$) for $V$ an invertible $m\times m$ matrix over $F$. Now, $t\left(P\right)=s\left(P\right)^T$ yields $s\left(P\right)=t\left(P\right)^T=\left(VPV^{-1}\right)^T = \left(V^{-1}\right)^TP^TV^T$. In other words, if we define $U=\left(V^{-1}\right)^T$, then $s\left(P\right)=UP^TU^{-1}$ for every matrix $P\in\mathrm{M}_m\left(F\right)$, and the Theorem is proven.

The official solution is actually quite nice, not algebraic at all. Here is the sketch.

Click to reveal hidden text

This is probably close to a record for the weirdest solution I've ever found on an olympiad problem. It's equivalent to show that $A_n = B_n$ where $A_n = 2^na_n$, $B_n = 2^nb_n$. In that case, $A_0 = B_0 = 1$, $A_1 = B_1 = 14$, and the recursion is $A_{n+1} = 8A_{n-1} + 6A_n$ or $A_{n+1} = 12A_{n-1} + 2A_n$. [asy][asy] size(6cm); int n = 7; for (int i=1; i <= n; ++i) { draw( (i,0)--(i-1,0)--(i-1,1)--(i,1)--cycle ); if (i <= 2) { MP("\epsilon_" + (string) i, (i,1), dir(90)); } if (i == n-2) { MP("\epsilon_{n-2}", (i,1), dir(90)); } if (i == n-1) { MP("\epsilon_{n-1}", (i,1), dir(90)); } } [/asy][/asy] Consider a mansion with $n$ rooms labelled $1, 2, \dots, n$ arranged in a row. There are $n-1$ walls; we label the wall between rooms $i$ and $i+1$ with $\epsilon_i$. Now, suppose we wish to paint each room of the mansion with one of fourteen colors, called, $\star, 1, 2, \dots, 13$. Note that each wall thus receives two colors. We do this subject to two strange rules. Suppose $i,j \neq \star$ are two colors of a wall. For walls labelled zero, we dictate that \[ i \in \left\{ j-2, j-1, j, j+1, j+2 \right\} \pmod{13}. \] For walls labelled one, we dictate that $i = j$. If a wall is marked $\star$, then there are no requirements. Note also that this is symmetric in $i$ and $j$ (so the mansion retains symmetry). We claim that $A_k$ counts the number of ways to paint the leftmost $k$ rooms of the mansion, while $B_k$ counts the number of ways to paint the rightmost $k$ rooms of the mansion. Let's look at just $A_k$ when $\epsilon_k = 0$. Suppose we've painted the first $k-1$ rooms with the colors $c_1, \dots, c_{k-1}$. Most of the time, we have $6$ colors we can select for $c_k$, five from the specified set plus the extra choice $\star$. However, if $c_{k-1} = \star$, we have an additional $8$ choices. This happens for $A_{k-2}$ mansions. The recursion $A_k = 6A_{k-1} + 8A_{k-2}$ follows. Now it's obvious $A_n = B_n$.

v_Enhance wrote: The recursion $A_k = 8A_{k-1} + 6A_{k-2}$ follows. I'm a bit confused, because this doesn't match $A_{n+1} = 8A_{n-1} + 6A_n$. Maybe you want to dictate \[ i \in \left\{ j-2, j-1, j, j+1, j+2 \right\} \pmod{13} \] for walls labelled zero, and \[ i = j \] for walls labelled one? Otherwise, this is a really nice solution!

Ah yes, I'm as careless as always. Thanks for pointing that out, I've edited the solution.

Here's my solution that I found a while ago. It's not very cool though... So given a string $w$ and 2 starting terms $a_0$ and $a_1$, if we apply the $w$ recursion to $a_0, a_1$, after $k$ steps we will have the number $c_k a_0 + d_k a_1$ for some integer coefficients $c_k, d_k$. Similarly, if we apply the first $k$ terms of $w$ backwards, then we get the number $e_k a_0 + f_k a_1$, where $e_k, f_k$ would be the backwards coefficients. The coefficients are unique to the string $w$. We induct on the length of $w$ (which is $n-1$). Assume that it's true for all lengths that are at most $n-2$. Note that by the inductive hypothesis, $c_k+7d_k = e_k+7f_k$ for $k \le n-2$. We do casework on the last term of the sequence. Say it's $0$ ($1$ goes exactly the same way). Evaluating from the front, we would get that $a_{n-2} = c_{n-3}+7d_{n-3} = e_{n-3}+7f_{n-3}$ and $a_{n-1} = c_{n-2}+7d_{n-2} = e_{n-2}+7f_{n-2}$. Applying the $0$ to these, we get that $a_n = 2a_{n-2}+3a_{n-1} = 2(e_{n-3}+7f_{n-3}) + 3(e_{n-2}+7f_{n-2})$. Now, going backwards, we first apply to $0$, so we now have the terms $1, 7, 23$. Now, this is equivalent to starting a sequence with $7, 23$ and doing the first $n-2$ terms backwards. So $b_n = 7e_{n-2}+23f_{n-2}$. So for $a_n = b_n$ to be true, $2(e_{n-3}+7f_{n-3}) + 3(e_{n-2}+7f_{n-2}) = 7e_{n-2}+23f_{n-2}$ and simplifying this gives $e_{n-3}+7f_{n-3} = 2e_{n-2}+f_{n-2}$. So proving this for any $w$ would finish this. But this is easy. Indeed, note that the RHS is equivalent to starting with $(2, 1)$ and evaluating the first $n-2$ steps backwards while the RHS is equivalent to starting a sequence with $(1, 7)$ and evaluating the first $n-3$ steps backwards. But starting with $(2, 1)$ gives the next term of $7$ under both operations, so we're done.

v_Enhance wrote: We claim that $A_k$ counts the number of ways to paint the leftmost $k$ rooms of the mansion, while $B_k$ counts the number of ways to paint the rightmost $k$ rooms of the mansion. Let's look at just $A_k$ when $\epsilon_k = 0$. Suppose we've painted the first $k-1$ rooms with the colors $c_1, \dots, c_{k-1}$. Most of the time, we have $6$ colors we can select for $c_k$, five from the specified set plus the extra choice $\star$. However, if $c_{k-1} = \star$, we have an additional $8$ choices. This happens for $A_{k-2}$ mansions. The recursion $A_k = 6A_{k-1} + 8A_{k-2}$ follows. What if $\epsilon_k = 1$? Wouldn't that add 1 more case? Also, v_Enhance, what is the motivation for your very beautiful solution? Thank you very much for all your help!

MathPanda1 wrote: What if $\epsilon_k = 1$? Wouldn't that add 1 more case? Yes, I just omitted it because this case is exactly the same; it gives you the other recursion. The idea was just that I wanted to see if I could get the relation to be symmetric from left to right in the way I did... because I wanted a combinatorial interpretation, I did the doubling to get the coefficients to be $12+2=8+6$. From there it amounted to putting the right restrictions on the walls in order to get the desired cases.

Thank you very much for the motivation v_Enhance! But I was wondering what the inspiration for using the walls and how you made such restrictions? Thank you again and look forward for your reply!

there is my solution. $ b_{n-i+1}=(3-2\varepsilon_{i})b_{n-i}+(2+\varepsilon_{i})b_{n-i-1}=\frac{-2a_{i+1}+7a_{i-1}}{-2a_{i}+a_{i-1}}b_{n-i}+\frac{a_{i+1}-7a_{i}}{-2a_{i}+a_{i-1}}b_{n-i-1} $ $ -2(a_{n-i}b_{i+1}-a_{n-i+1}b_{i})+(a_{n-i-1}b_{i+1}-a_{n-i+1}b_{i-1})-7(a_{n-i-1}b_{i}-a_{n-i}b_{i-1})=0 $ $ 2(a_{n-i}b_{i+1}-a_{n-i+1}b_{i})-(a_{n-i-1}b_{i+1}-a_{n-i}b_{i})=(a_{n-i}b_{i}-a_{n-i+1}b_{i-1})-7(a_{n-i-1}b_{i}-a_{n-i}b_{i-1})=0 $ plus them for $ i=1,2,\dots n-2 $ and we can get $ 13(b_{n}-a_{n})=0 $ which is $ b_{n}=a_{n} $

Here's a really weird solution! We define the sequence $P_0, \cdots, P_n$ of multivariate polynomials as follows: $P_0=1, P_1=7$ and $P_{i+1} = (2+x_i)P_{i-1}+(3-2x_i)P_i$ for $i=1,\cdots, n-1$. Note that $x_i=0$ corresponds to $\varepsilon_i=0$ and $x_i=1$ corresponds to $\varepsilon_i=1$. We're done if we can show that $P_n(x_1, \cdots, x_{n-1}) = P_n(x_{n-1}, \cdots, x_1)$. Now this follows if we can prove it with the restrictions that $x_i\in \left\{-2, \frac{3}{2}\right\}$, for all $i=1,\cdots, n-1$. Observe that $P_0=1, P_1=7$, $P_{i+1}=7P_i$ if $x_i=-2$, and $P_{i+1}=\frac{7}{2}P_{i-1}$ if $x_i = \frac{3}{2}$. We want to show that $P_n$ is the same if we reverse the order of the $x_i$. Let $d_i$ be the power of $7$ in $P_i$. We have $d_0=0, d_1=1$, $d_{i+1}=d_i+1$ if $x_i=-2$, and $d_{i+1}=d_{i-1}+1$ if $x_i=\frac{3}{2}$. This is an increasing sequence where the difference between consecutive terms is either $0$ or $1$. Consider the blocks of $-2$'s and $\frac{3}{2}$'s. A $-2$ will always cause an increase by $1$ from the previous term. A block of $k$ $\frac{3}{2}$'s, starting at $x_i$, will cause an increase of $\left\lfloor \frac{k}{2} \right\rfloor$ from $d_i$. So if we reverse everything the amount of each increase is still the same, just occurs in a different order, so $P_n$ will have the same power of $7$. A similar argument can be done for powers of $2$, and we can then conclude that $P_n$ is the same upon reversing the $x_i$.

From ideas similar to $\textbf{darij grinberg}$ we see how to construct more similar problems : First we need to chose some symmetrical matrices $A_1, A_2, \ldots, A_n$ and vector $v$. So we get relation $v^TA_1A_2\ldots A_n v = v^TA_nA_{n-1}\ldots A_1 v$. Next for every invertible $U$ we have $v_1^T A'_1A'_2\ldots A_n v_2 = v_1^TA'_nA'_{n-1}\ldots A'_1 v_2$, where $A'_i := UA_iU^{-1}, v_1^T := v^T U^{-1}, v_2 :=Uv$. And (conjecturally) all such examples can be constructed in this way.

Similar approach to lemniscate's. The problem itself is very similar to USAJMO 2011/4. Define the polynomials $P_n$ inductively by $P_0 = 1$, $P_1 = 7$, and \[ P_n = (2+x_{n-1})P_{n-2} + (3-2x_{n-1})P_{n-1} \]for $n\geq 0$. We will show that $P_n(x_1,\ldots, x_{n-1}) = P_n(x_{n-1},\ldots, x_1)$ as well. We proceed by strong induction on $n$; the base cases of $n=1,2,3,4,5$ are easily checked by hand. For the inductive step, note that \[ P_n(x_1,\ldots, x_{n-1}) = (2+x_{n-1})P_{n-2}(x_1,\ldots, x_{n-3}) + (3-2x_{n-1})P_{n-1}(x_1,\ldots, x_{n-2}). \]Now, \[ \begin{aligned} P_n(x_{n-1}, \ldots, x_1) &= (2+x_1)P_{n-2}(x_{n-1},\ldots, x_3) + (3-2x_1)P_{n-1}(x_{n-1},\ldots, x_2)\\ &= (2+x_1)P_{n-2}(x_3,\ldots, x_{n-1}) + (3-2x_1)P_{n-1}(x_2,\ldots, x_{n-1}). \qquad \qquad (\spadesuit) \end{aligned} \]Now, \[ P_{n-1}(x_2,\ldots, x_{n-1}) = (2+x_{n-1})P_{n-3}(x_2,\ldots, x_{n-3}) + (3-2x_{n-1})P_{n-2}(x_2,\ldots, x_{n-2}), \]and \[ P_{n-2}(x_3,\ldots, x_{n-1}) = (2+x_{n-1})P_{n-4}(x_3,\ldots, x_{n-3}) + (3-2x_{n-1})P_{n-3}(x_3,\ldots, x_{n-2}). \]Substituting into $(\spadesuit)$ and collecting $(2+x_{n-1})$ and $(3-2x_{n-1})$ terms, we see that \[ P_n(x_{n-1},\ldots, x_1) = (2+x_{n-1})((2+x_1)P_{n-4}(x_3,\ldots, x_{n-3})+(3-2x_1)P_{n-3}(x_2,\ldots, x_{n-3}))\]\[+(3-2x_{n-1})((2+x_1)P_{n-3}(x_3,\ldots, x_{n-2}) + (3-2x_1)P_{n-2}(x_2,\ldots, x_{n-2})). \]The first collapses into \[ (2+x_{n-1})((2+x_1)P_{n-4}(x_{n-3},\ldots, x_{3})+(3-2x_1)P_{n-3}(x_{n-3},\ldots, x_2))\]\[= (2+x_{n-1})P_{n-2}(x_{n-3},\ldots, x_1) = (2+x_{n-1})P_{n-2}(x_1,\ldots, x_{n-3}), \]while the latter collapses into \[ (3-2x_{n-1})((2+x_1)P_{n-3}(x_{n-2},\ldots, x_{3}) + (3-2x_1)P_{n-2}(x_{n-2},\ldots, x_{2}))\]\[ = (3-2x_{n-1})P_{n-1}(x_{n-2},\ldots, x_1) = (3-2x_{n-1})P_{n-1}(x_1,\ldots, x_{n-2}), \]which when summed equals $P_n(x_1,\ldots, x_{n-1})$. $\blacksquare$

Another boring inductive solution: let $f_0 (a_{i-1}, a_i) = 2a_{i-1}+3a_i, f_1 (a_{i-1}, a_i) = 3a_{i-1}+a_i$. We'll abuse notation by letting a "word" be any sequence $W=f_{\epsilon_k}f_{\epsilon_{k-1}}...f_{\epsilon_0}$ where $W(a_0, a_1)$ is the $k+1$th term of the sequence $\{a_i\}$ given by the corresponding choice of $\epsilon_i$. Note that this matches with our earlier definition when $k=0$. We'd like to show $W(1,7)=\overline{W}(1,7)$, where $\overline{W}$ denotes reversing the order. We'll induct on the length of $W$ with base cases $1,2$ obvious. For the inductive step, it's enough to show that if $A,B\in \{f_0, f_1\}$, then $ABW(1,7) = \overline{W}BA(1,7)$. Note that $\overline{W}BA(1,7) = \overline{W}(A(1,7), BA(1,7))$ and $ABW(1,7) = A(W(1,7), BW(1,7))=A(W(1,7), \overline{W}B(1,7))$ so it's enough to show these latter quantities are equal. Suppose $W(a_0, a_1) = ua_0+va_1$ and $\overline{W} (a_0, a_1) = u'a_0+v'a_1$; then by the inductive hypothesis, we have $u+7v = u'+7v'$. Case 1: $A=B=f_0$. Then $A(W(1,7), \overline{W}B(1,7)) = A(u+7v, \overline{W}(7,23)) = A(u+7v, 7u' + 23v') = 2(u+7v) + 3(7u' + 23v')$. Meanwhile $\overline{W}BA(1,7) = \overline{W}(23, 83) = 23u'+83v'$; utilizing the fact that $u+7v=u'+7v'$ proves the equality. Case 2: $A=B=f_1$. Then $A(W(1,7), \overline{W}B(1,7)) = A(u+7v, \overline{W} (7, 10)) = A(u+7v, 7u' + 10v') = 3(u+7v)+(7u'+10v')$; meanwhile $\overline{W}BA(1,7) = \overline{W} (10, 31) = 10u'+31v'$, so again the equality holds. Case 3: $A=f_0, B=f_1$. Then $A(W(1,7), \overline{W}B(1,7)) = A(u+7v, \overline{W}(7,10)) = A(u+7v, 7u' + 10v') = 2(u+7v) + 3(7u' + 10v')$; meanwhile $\overline{W}BA(1,7) = \overline{W} (23, 44) = 23u'+44v'$, so again the equality holds. Case 4: $A=f_1, B=f_0$. Then $A(W(1,7), \overline{W}B(1,7)) = A(u+7v, \overline{W} (7, 23)) = A(u+7v, 7u'+23v') = 3(u+7v) + (7u'+23v')$; meanwhile $\overline{W}BA(1,7) = \overline{W} (10, 44) = 10u'+44v'$, so again the desired equality holds. In all four cases, we're done, so the inductive step is complete as desired.

I did the 4 case induction but I have a solution idea that involves combo: I realized that $7=3*1+2*2=1*1+3*2$(If we have 2,1 then the next term will always be 7), this gives an intuition to build a new sequence. Thus, lets create a new sequence, $x_k=\frac{a_k}{2^{n-k}}$ and $y_k=\frac{b_k}{2^{n-k}}$ Now we have $x_k=6x_{k-1}+8x_{k-2}$ if e is 0, and $x_k=2x_{k-1}+12x_{k-2}$ if e is 1. Same for $y_k$. This is nice because the 2 numbers sum to 14 in both cases. I think we need to do something with recursion that is symmetrical? If anybody has any ideas how to finish, please tell me.

Terribly written up solution, but this is exactly how I thought of it when solving the problem. Note that \[a_{i+1} = (2+\varepsilon_i)a_{i-1} + (3-2\varepsilon_i)a_i\]and \[a_{i+1} = (2+\varepsilon_{n-i})a_{i-1} + (3-2\varepsilon_{n-i})a_i.\]Using these relations without plugging in $\varepsilon_i=0,1$, we see that $a_n$ and $b_n$ are both $(n-1)$-degree polynomials in $\varepsilon_1,\ldots,\varepsilon_{n-1}$. Furthermore, each term is squarefree by a trivial induction. It suffices to show that the polynomial for $a_n$ is symmetric under a $(\varepsilon_1,\ldots,\varepsilon_{n-1})\to(\varepsilon_{n-1},\ldots,\varepsilon_1)$ interchange. It is intuitively clear that it suffices to show this for all $(\varepsilon_1,\ldots,\varepsilon_{n-1})\in\{x,y\}^{n-1}$ for some fixed $x$ and $y$, but we'll formally prove this by an application of Combinatorial Nullstellensatz. Claim: Suppose we have a squarefree polynomial $P(x_1,\ldots,x_m)$ of degree at most $m$ such that it is zero for all $(x_1,\ldots,x_m)\in\{x,y\}^m$ for some fixed $x$ and $y$. Then, $P$ is identically $0$. Proof: Suppose not, so let the degree be $d$, and let a term of maximal degree be $x_{i_1}\cdots x_{i_d}$. By CNS, there is some $(x_1,\ldots,x_n)\in\prod S_i$ where $S_{i_k}=\{x,y\}$ and $S_i=\{x\}$ for $i\ne i_k$ for any $i$ such that \[P(x_1,\ldots,x_n)\ne 0.\]This is a contradiction, so we're done. $\blacksquare$ We may now assume that $\varepsilon_i\in\{-2,\tfrac{3}{2}\}$. We now have $a_{i+1}=7a_i$ if $\varepsilon_i=-2$ and $a_{i+1}=\frac{7}{2}a_{i-1}$ if $\varepsilon_i=\tfrac{3}{2}$. Let $\delta_i=1$ if $\varepsilon_i=-2$ and $\delta_i=2$ if $\varepsilon_i=\tfrac{3}{2}$. Thus, to find the value of $a_n$, we perform the following algorithm with $a_n$ initially set to $1$. Consider the number line and start at position $n$. From position $i$, jump to $i-\delta_i$, and if $\delta_i=1$, update $a_n$ to $7a_n$, and if $\delta_i=2$, update $a_n$ to $7a_n/2$. If we stop at $1$, then update $a_n$ to $7a_n$, and if we stop at $0$, then we just output $a_n$ without any change. It suffices to show that this process gives the same value of $a_n$ if we reverse the initial sequence of $\delta_i$s. It's not hard to see that the final value of $a_n$ we get is $7^{n-x}2^{-x}$, where $x$ is the number of times we land on $i$ with $\delta_i=2$. Thus, it suffices to show that the process gives the same value for $x$ if we flip the sequence. Indeed, it is not hard to see that \[x=\sum_{B}\lceil f(B)/2\rceil,\]where $B$ ranges over all blocks of consecutive $2$s, and $f(B)$ is the size of the block. This stays the same if we flip the sequence, so we're done.

Nice problem. Probably a new solution. Note \begin{align*} a_{i+1} &= (3-2\varepsilon_i)a_i+(2+\varepsilon_i)a_{i-1}. \qquad (\spadesuit) \end{align*}Starting with $a_0=1$ and $a_1=7$, using the above process we can write $a_k$ as a polynomial in $\varepsilon_1,\ldots,\varepsilon_{k-1}$. It suffices to prove that this polynomial is invariant when we replace $\varepsilon_1,\ldots,\varepsilon_{k-1}$ with $\varepsilon_{k-1},\ldots,\varepsilon_1$, respectively (i.e. reverse the list of variables), since for all $n$, $b_n$ is constructed in the same way as $a_n$ but $\varepsilon_{n-i}$ is used wherever $\varepsilon_i$ is used instead. So now we can forget about the $b$ sequence entirely!

Example: first few terms of polynomial sequence

Fix an arbitrary $n$. Observation 1. The polynomial for $a_n$ is squarefree in terms of the variables. This is clear since to generate $a_{i+1}$, we take a linear combination of the polynomials $a_i$ and $a_{i-1}$ whose coefficients are in terms of the new variable $\varepsilon_i$. Observation 2. By Observation 1, each term in the polynomial form of $a_n$ has either 0 or 1 of each of $\varepsilon_1,\ldots,\varepsilon_{n-1}$ multiplied together times some constant coefficient. So we can express $a_n$ as a table where each binary string of length $n-1$ has a corresponding coefficient.

Example: first few tables

Now, let's analyze the recursive equation $(\spadesuit)$ in terms of the binary table. We have \[ a_{n+1} = 3a_n- 2\varepsilon_n a_n + 2a_{n-1} + 1\varepsilon_n a_{n-1}. \]So to generate the table for $a_{n+1}$ from previous tables: Take the binary strings of $a_n$ and add $0$ to the end. Multiply the values all by $3$. Take the binary strings of $a_n$ and add $1$ to the end. Multiply the values all by $-2$. Take the binary strings of $a_{n-1}$ and add $00$ to the end. Multiply the values all by $2$. Take the binary strings of $a_{n-1}$ and add $01$ to the end. Multiply the values all by $1$. Finally, vector sum everything (sum up all the values for each specific binary string from the above process) to get the final table for $a_{n+1}$. We can restate the problem as a combinatorics problem now similar to above: Combo problem wrote: Define the function $f:\text{binary strings} \to \mathbb{Z}$ as follows: $f(\emptyset)=7$, $f(0)=23$, $f(1)=-13$, and \begin{align*} f(S) &= \mathbf{1}(\text{$S$ ends in 0}) \cdot 3f(S-0) \\ &~ + \mathbf{1}(\text{$S$ ends in 1}) \cdot (-2)f(S-1) \\ &~ + \mathbf{1}(\text{$S$ ends in 00}) \cdot 2f(S-00) \\ &~ + \mathbf{1}(\text{$S$ ends in 01}) \cdot 1f(S-01), \end{align*}Prove $f(S)=f(\overline{S})$ for all binary strings $S$. (Here, $S-S'$ denotes removing $S'$ from the end of $S$ if it's there. And $\overline{S}$ denotes the reverse of $S$.) We go by induction on the length of $S$. Brute force to prove the statement for all $S$ of length at most 4 (by writing out the table as shown in the example above). Main idea: We split into cases based on the first two and last two characters in the binary string. Use the inductive hypothesis heavily. Sketch of finish. There's not much to the combo problem after this idea, so the remaining case-bash is a sketch. The first few cases are computed explicitly, but the rest can be filled in and are extremely similar to each other.

Case 1: 00S00

This is equal to $f(00\overline{S}00)$ since the two middle terms have the same coefficient.

Case 2: 00S01

10S00

These are equal.

Case 3: 00S10[hide]Comes out to $9f(1\overline{S})+6f(1\overline{S})$. Not going to write up, but very similar process to the rest (plug into rule and simplify).[/hide] 01S00

These are equal.

Case 4: 00S11

11S00

These are equal.

Case 5: 01S01[hide]Not going to write up, but very similar process to the rest (plug into rule and simplify).[/hide] 10S10

These are equal.

Case 6: 01S10

Equal to its reverse.

Case 7: 01S11[hide]Not going to write up, but very similar process to the rest (plug into rule and simplify).[/hide] 11S10

These are equal.

Case 8: 10S01

Equal to its reverse.

Case 9: 10S11[hide]Not going to write up, but very similar process to the rest (plug into rule and simplify).[/hide] 11S01

These are equal.

Case 10: 11S11

Equal to its reverse. This finishes the induction, and the proof.

Remarks

We strong induct on $n$. The base cases $n=1,2$ are trivial and $n=3$ is easy to check. First, for two linear functions $k(x,y)$ and $\ell(x,y)$, define their composition $k\circ \ell(x,y) = \ell(y,k(x,y))$. Restating the problem, let $n\ge 4$, $k_0(x,y) = 2x + 3y$ and $k_1(x,y) = 3x + y$. We have the linear functions $a = k_{\epsilon_1}\circ \dots \circ k_{\epsilon_{n-1}}$ and $b = k_{\epsilon_{n-1}}\circ \dots\circ k_{\epsilon_1}$ (with order of operations from left to right), and we want to show $a(1,7) = b(1,7)$. By the inductive hypothesis, $a'(1,7) = b'(1,7)$ and $a''(1,7) = b''(1,7)$ where $a' = k_{\epsilon_1}\circ \dots \circ k_{\epsilon_{n-2}}$, $a'' = k_{\epsilon_1}\circ \dots \circ k_{\epsilon_{n-3}}$, $b' = k_{\epsilon_{n-2}}\circ \dots\circ k_{\epsilon_1}$, and $b'' = k_{\epsilon_{n-3}}\circ \dots\circ k_{\epsilon_1}$. If $\epsilon_n = 0$, we have $$a(1,7) = 2a''(1,7) + 3a'(1,7) = 2b''(1,7) + 3b'(1,7) = 2b'(2,1) + 3b'(1,7) = b'(7,23) = k_{\epsilon_n}\circ b'(1,7) = b(1,7).$$ If $\epsilon_n = 1$, we have $$a(1,7) = 3a''(1,7) + a'(1,7) = 3b''(1,7) + b'(1,7) = 3b'(2,1) + b'(1,7) = b'(7,10) = k_{\epsilon_n}\circ b'(1,7) = b(1,7).$$

The arch $20\%$ hint led me to this monstrosity, so at least I can divert some blame. Let $x_n = 2^n a_n$ and $y_n = 2^n b_n$ for each $n$. Then the existing recurrences read \[x_n \in \{12x_{n-2} + 2x_{n-1}, 6x_{n-2} + 8x_{n-1}\}.\]This satisfies the important (!) property that $12+2=7 \cdot 2 = 6+8$. In particular, we consider the following totally not contrived combinatorial problem: New Problem wrote:

We have a line of $n$ cells delimited by $n-1$ walls, some of which are weak. We want to color some (not necessarily all) of the $n$ cells using $13$ different colors

, such that the following rules are satisfied: If two colored cells are delimited by a weak wall, then they must be the same color; If two colored cells are delimited by a strong wall, then they must be within two spaces of each other on the color wheel (we have to insert black somewhere random on the wheel unfortunately.) We let wall $i$ from the left be weak if $\varepsilon_i = 1$. We let $x_i$ denote the number of ways to color the first $i$ cells from the left, and $y_i$ the number of ways to color the first $i$ cells from the right. Then consider: If the $i$th cell from the left is delimited by a weak wall from the $i-1$th cell, we can either leave it colorless, yielding $x_{i-1}$ colorings. If we color the cell, we have one of two cases: The $i-1$th cell is colored that same color. Then our problem bijects to coloring the first $i-1$ cells in the obvious way, except that the $i-1$th cell cannot be left colorless. Hence, there are $x_{i-1} - x_{i-2}$ cases here. The $i-1$th cell is left colorless. Then we just need to color the remaining $i-2$ cells, yielding $13x_{i-2}$ cases for the $13$ possible colorings of the last cell. So this case yields $x_i = 2x_{i-1} + 12x_{i-2}$, which is what we want. If the $i$th cell from the left is delimited by a strong wall from the $i-1$th wall, we can again either leave it colorless, yielding $x_{i-1}$ colorings. Otherwise: If the $i-1$th cell is also colored, there are $5$ ways to color it and we have again a bijection to the $i-1$ case because the colors are symmetric! So there are $5\left(x_{i-1}-x_{i-2}\right)$ colorings here. If the $i-1$th cell is left uncolored, there are again $13x_{i-2}$ ways total to color the first $i-2$ cells. Thus this case yields $x_i = 6x_{i-1} + 8x_{i-2}$, which is also what we want. Now observe that both conditions are symmetric, so we get the same recursion for $\{y_i\}$. As $x_1 = y_1 = 14$, $x_n$ and $y_n$ both count the number of ways to color the entire line, which means that they are equal. Remark: The problem works (in the $\{x_i\}$ statement) in general as long as the recursion reads \[x_n \in \{2a x_{n-1} + (k-2a)x_{n-2}, 2b x_{n-1} + (k-2b)x_{n-2}\}.\]In this case, the two types of walls permit colors with distance within $a-1$ and within $b-1$, respectively. Remark: Although this solution is slick, I think it's almost impossible to find. I was told to make the $x_n = 2^n a_n$ substitution, and even after embarking on the combinatorial construction route, finding the actual construction took me more than four hours. In particular, the idea of making a ``colorless" color and making the other $13$ colors symmetric, which is the heart of the construction, is not natural at all to come by. In hindsight, the strong induction approach seems much easier, but my brain got hooked on ``hey this looks like a combinatorial recursion" almost immediately, so oh well.