Problem 4 : 2 sequences

Basically the same as 2009 C3.

By interpreting the $u_i$ and $v_i$ as multilinear polynomials, it suffices to solve the problem in the special case where $a_k \in \{ -\tfrac 14, 0\}$ . Define $x_k = 2^k u_k$ and $y_k = 2^k v_k$ . We consequently have that

$x_{k+1} = \begin{cases} 2x_k - x_{k-1} & \text{if } a_k = -\tfrac14 \\ 2x_k & \text{otherwise}. \end{cases}$

Consider a mansion with $n$ rooms in a line, numbered $R_1$ , $R_2$ , $\dots$ , $R_n$ . We wish to paint each room either black or white in such a manner that if $a_k = -\tfrac 14$ , then $R_k$ and $R_{k+1}$ cannot both be black when $k$ is odd, and cannot both be white when $k$ is even.

Now it's easy to see that $x_k$ then counts the number of ways to paint the first $k$ rooms. Similarly, $y_k$ then counts the number of ways to paint the last $k$ rooms. Thus $x_n = y_n$ .