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, \ldots, 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$.

So we start off by listing off the first few $u$'s: \begin{align*} u_1 &= 1 \\ u_2 &= 1 + a_1 \\ u_3 &= 1 + a_1 + a_2 \\ u_4 &= 1 + a_1 + a_2 + a_3 + a_1a_3 \\ u_5 &= 1 + a_1 + a_2 + a_3 + a_4 + a_1a_3 + a_1a_4 + a_2a_4 \end{align*} The problem is equivalent to showing that $u_n$ is symmetric (i.e. switiching all the $a_i$ with $a_{n-i}$ will still give the same $u_n$). Now notice that each of the $u$s has a $1$; this is easy to prove inductively. Each one also has a $a_1 + a_2 + \cdots + a_{n-1}$ which can also be proven inductively: $u_{n+1} = u_n + a_nu_{n-1}$ and since we know that each $u$ has a $1$, that $a_n$ gets added on to the sum in $u_n$. Now notice that the indicies of the $a$s in each term that is a product of more than one $a_i$ differs by at least $2$. In other words, if there is a term in the sum that is $a_{i_1}a_{i_2}\cdots a_{i_k}$ with $i_1 < i_2 < \cdots < i_k$, then $i_2 - i_1 \ge 2$, $i_3 - i_2 \ge 2$,..., $i_k - i_{k-1} \ge 2$. This can be proven with induction: Suppose that we have $u_n = 1 + a_1 + a_2 + \cdots$ where every term in $u_n$ is the product of $a$'s such that the indices differ by at least $2$. Multiplying $u_{n-1}$ by $a_n$ will also preserve that condition; $u_{n-1}$ can only use $a_1, a_2, ..., a_{n-2}$. Furthermore, every single possibility will be covered. Adding this onto $u_n$ gives us the desired result. Hence all the indices differ by at least $2$. Now we just show that this is symmetric. Suppose we again have some term $a_{i_1}a_{i_2}\cdots a_{i_k}$ in $u_n$ where each $i$ is less than $n$. Then, after we "reflect", we would get $a_{n - i_1}a_{n - i_2}\cdots a_{n - i_k}$; clearly the difference between each is still at least $2$, so that term also exists in $u_n$. Therefore, $u_n$ is symmetric, as desired.

We use notation $S(x,y)[\alpha_1,\cdots,\alpha_{n-1}]$ to denote $x_n$ with $x_0=x,x_1=y,x_{i+1}=x_i+\alpha_ix_{i-1},i=1,\cdots,n-1$. Here are a few easy facts: 1) $u_n=S(1,1)[a_1,\cdots,a_{n-1}]$ 2) $v_n=S(1,1)[a_{n-1},\cdots,a_{1}]$ 3) $S(x,y)[\alpha_1,\cdots,\alpha_{n-1}]$ is a linear function of $x,y$ once $\alpha_i$ are fixed 4) $S(x,y)[\alpha_1,\cdots,\alpha_{n-1}]=S(y,y+\alpha_1x)[\alpha_2,\cdots,\alpha_{n-1}]$ 5) $S(x,y)[\alpha_1,\cdots,\alpha_{n-1}]=S(x,y)[\alpha_1,\cdots,\alpha_{n-2}]+\alpha_{n-1}S(x,y)[\alpha_1,\cdots,\alpha_{n-3}]$ Now we will prove it with induction. It is trivial for $n=2,3$. Suppose it holds for $n\le N$, $u_{N+1}=S(1,1)[a_1,\cdots,a_{N}]=S(1,1)[a_1,\cdots,a_{N-1}]+a_N*S(1,1)[a_1,\cdots,a_{N-2}]$ $v_{N+1}=S(1,1)[a_N,\cdots,a_1]=S(1,1+a_N)[a_{N-1},\cdots,a_1]\\= S(1,1)[a_{N-1},\cdots,a_1]+S(0,a_N)[a_{N-1},\cdots,a_1]\\= S(1,1)[a_{N-1},\cdots,a_1]+a_N*S(0,1)[a_{N-1},\cdots,a_1]\\= S(1,1)[a_{N-1},\cdots,a_1]+a_N*S(1,1)[a_{N-2},\cdots,a_1]$ We see $u_{N+1}=v_{N+1}$ by induction assumptions.

Combinatorially argumentive solutions are always nice and deserve credit,though I solved it in a simple way: First let us investigate what is $u_i$.By testing the initial values it is easy to observe that perhaps it is like this: $1+\sum{a_i}+\sum_{i_1,i_2,\dots,i_j}{a_{i_1}a_{i_2}\cdots a_{i_j}}$ where the sum runs over all the suffixes that have difference of atleast 2. Approaching by induction we see that this is indeed the case!! Now for $v_i$ it is like a similar expression.Then note that both the expressions are basically the same for $i=n$.So we are done.

First, we will establish a formula for $u_k$. Let $\mathcal{F}_n$ denote the complete family of subsets $S$ of $\{1,2,\cdots,n\}$ such that either $|S|=1$ or for any two distinct elements $s_1,s_2\in S$ we have $|s_1-s_2|\geq 2$. Then I claim \[u_k=1+\sum_{S\in\mathcal{F}_{k-1}}\prod_{t\in S}a_t.\] Notice how each term on the RHS corresponds uniquely to a subset in $\mathcal{F}_{k-1}$, with the $1$ essentially acting as the empty set. (More specifically, notice the bijection $\{1,2,\cdots,k-1\}\to\{a_1,a_2,\cdots,a_{k-1}\}$ and multiply all the elements in a subset of the latter set.) To prove this, we use strong induction. The base cases $k=1$ and $k=2$ are trivial. Now for the inductive step, assume that the recursion holds for all $1\leq k_0\leq k$. To proceed further, we need to determine exactly how to find the family $\mathcal{F}_k$. Let $S$ be a subset of $\mathcal{F}_k$; then either two cases occur. If $k\not\in S$, then all the elements of $S$ are free to come from $\mathcal{F}_{k-1}$; otherwise, the members of $S$ include $k$ as well as any elements/subsets chosen freely from $\mathcal{F}_{k-2}$ (including the so-called "empty set", as this will produce the $a_{k}$ term). Constructing the bijection as stated in the end of the first paragraph means that the corresponding expression for $\mathcal{F}_{k}$ case is \[1+\sum_{S\in\mathcal{F}_{k-1}}\prod_{t\in S}a_t+a_{k}\left(1+\sum_{S\in\mathcal{F}_{k-2}}\prod_{t\in S}a_t\right),\] which is itself equal to $u_k+a_ku_{k-1}=u_{k+1}$! This completes the induction. This trivializes the original problem. Note that due to symmetry the final expression for $u_n$ is invariant under the involution $a_i\to a_{n-i}$, and $v_n$ is equivalent to $u_n$ under such a "reversal of coefficients". Hence $u_n=v_n$ as desired.

Outline: We first prove a powerful lemma that will be useful later on in the problem. We then transform the recurrence relations into matrix products. The lemma then kills the problem. More detail follows: Lemma: For positive integer $k$, define matrices $U_k$ and $V_k$ as follows: \[U_k = \left(\begin{array}{cc} u_{11}^k & u_{12}^k \\ \\ u_{21}^k & u_{22}^k \end{array}\right) = \left(\begin{array}{cc} 1 & a_k \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} 1 & a_{k - 1} \\ 1 & 0 \end{array}\right)...\left(\begin{array}{cc} 1 & a_1 \\ 1 & 0 \end{array}\right).\]\[V_k = \left(\begin{array}{cc} v_{11}^k & v_{12}^k \\ \\ v_{21}^k & v_{22}^k \end{array}\right) = \left(\begin{array}{cc} 1 & a_1 \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} 1 & a_2 \\ 1 & 0 \end{array}\right)...\left(\begin{array}{cc} 1 & a_k \\ 1 & 0 \end{array}\right).\] Then we have the following relations: $\quad$ $v_{11}^k = u_{21}^k + u_{22}^k; \quad v_{11}^k + v_{12}^k = u_{11}^k + u_{12}^k.$ Proof. We proceed by induction on $k.$ The base case, $k = 1$, is obvious. Now, for the inductive hypothesis, we assume the claim to be true for some integer $k = m$, and prove the claim true for $k = m + 1.$ We have the following two expressions for $U_{m + 1}$ and $V_{m + 1}$: \[U_{m + 1} = \left(\begin{array}{cc} 1 & a_{m + 1} \\ 1 & 0 \end{array}\right)U_m = \left(\begin{array}{cc} 1 & a_{m + 1} \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} u_{11}^m & u_{12}^m \\ \\ u_{21}^m & u_{22}^m \end{array}\right)\]\[= \left(\begin{array}{cc} u_{11}^m + a_{m + 1}u_{21}^m & u_{12}^m + a_{m + 1}u_{22}^m \\ \\ u_{11}^m & u_{12}^m \end{array}\right).\]\[V_{m + 1} = V_m\left(\begin{array}{cc} 1 & a_{m + 1} \\ 1 & 0 \end{array}\right) = \left(\begin{array}{cc} v_{11}^m & v_{12}^m \\ \\ v_{21}^m & v_{22}^m \end{array}\right) \left(\begin{array}{cc} 1 & a_{m + 1} \\ 1 & 0 \end{array}\right)\]\[= \left(\begin{array}{cc} v_{11}^m + v_{12}^m & a_{m + 1}v_{11}^m \\ \\ v_{21}^m + v_{22}^m & a_{m + 1}v_{21}^m \end{array}\right).\] To verify the claim, we check the two conditions, specified above, in order: The first condition is true, because we have $\quad$ $\left(v_{11}^m + v_{12}^m\right) = \left(u_{11}^m\right) + \left(u_{12}^m\right)$ $\quad$ by the induction hypothesis. The second condition is true, because, by the induction hypothesis, we have \[\left(v_{11}^m + v_{12}^m\right) + \left(a_{m + 1}v_{11}^m\right) = v_{11}^m + v_{12}^m + a_{m + 1}\left(u_{21}^m + u_{22}^m\right)\]\[= \left(u_{11}^m + a_{m + 1}u_{21}^m\right) + \left(u_{12}^m + a_{m + 1}u_{22}^m\right).\] Therefore, we have shown that the claim holds for $k = m + 1.$ This completes the induction. $\quad$ $\blacksquare$ Now, for the main proof. By the given condition, we have, for all positive integers $k$, \[\left(\begin{array}{c} u_{k + 1} \\ u_k \end{array}\right) = \left(\begin{array}{cc} 1 & a_k \\ 1 & 0 \end{array}\right)\left(\begin{array}{c} u_k \\ u_{k - 1} \end{array}\right).\] By repeated applications of the above identity, it follows that \[\left(\begin{array}{cc} u_n \\ u_{n - 1} \end{array}\right) = \left(\begin{array}{cc} 1 & a_{n - 1} \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} u_{n - 1} \\ u_{n - 2} \end{array}\right)\]\[= \left(\begin{array}{cc} 1 & a_{n - 1} \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} 1 & a_{n - 2} \\ 1 & 0 \end{array}\right)\left(\begin{array}{cc} u_{n - 2} \\ u_{n - 3} \end{array}\right)\]\[= ... = U_{n - 1}\left(\begin{array}{c} u_1 \\ u_0 \end{array}\right) = \left(\begin{array}{cc} u_{11}^{n - 1} & u_{12}^{n - 1} \\ \\ u_{21}^{n - 1} & u_{22}^{n - 1} \end{array}\right)\left(\begin{array}{c} 1 \\ 1 \end{array}\right)\]\[= \left(\begin{array}{c} u_{11}^{n - 1} + u_{12}^{n - 1} \\ \\ u_{21}^{n - 1} + u_{22}^{n - 1} \end{array}\right).\] Similarly, we find that \[\left(\begin{array}{c} v_n \\ v_{n - 1} \end{array}\right) = V_{n - 1}\left(\begin{array}{c} v_1 \\ v_0 \end{array}\right) = \left(\begin{array}{c} v_{11}^{n - 1} + v_{12}^{n - 1} \\ v_{21}^{n - 1} + v_{22}^{n - 1} \end{array}\right).\] By equating entries in the matrices, it follows that $u_n = u_{11}^{n - 1} + u_{12}^{n - 1}$ $\quad$ and $\quad$ $v_n = v_{11}^{n - 1} + v_{12}^{n - 1}.$ However, by our Lemma, we have $\quad$ $u_{11}^{n - 1} + u_{12}^{n - 1} = v_{11}^{n - 1} + v_{12}^{n - 1} \implies u_n = v_n.$ The proof is complete. $\quad$ $\blacksquare$

my solution : at first, we will prove for $ n=i+j $, $ v_{i}u_{j}+(v_{i+1}-v_{i})u_{j-1}=v_{i+1}u_{j-1}+(v_{i+2}-v_{i+1})u_{j-2} $ <pf> $ LHS=v_{i}(u_{j-1}+a_{j-1}u_{j-2})+(v_{i+1}-v_{i})u_{j-1}=v_{i+1}u_{j-1}+v_{i}a_{j-1}u_{n-i-2}=v_{i+1}u_{j-1}+(v_{i+2}-v_{i+1})u_{j-2} $ back to the problem, we have $ u_{n}=v_{0}u_{n}+(v_{1}-v_{0})u_{n-1} $ with $ i=0,j=n $ so $ u_{n}=v_{n-1}u_{1}+(v_{n}-v_{n-1})u_{0}=v_{n} $

Does this work? We have $a_{n-k}=\frac{u_{n-k+1}-u_{n-k}}{u_{n-k-1}}=\frac{v_{k+1}-v_k}{v_{k-1}}$ Let's write above for $k=1,2,...,n-1$ for $k=1$ $(u_n-u_{n-1}) v_0=(v_2-v_1) u_{n-2}$ ......... ......... for $k=n-1$ $(u_2-u_1) v_{n-2}=(v_n-v_{n-1}) u_0$ Now if we sum them we will get $u_n=v_n$

tenplusten wrote: Does this work? We have $a_{n-k}=\frac{u_{n-k+1}-u_{n-k}}{u_{n-k-1}}=\frac{v_{k+1}-v_k}{v_{k-1}}$ Let's write above for $k=1,2,...,n-1$ for $k=1$ $(u_n-u_{n-1}) v_0=(v_2-v_1) u_{n-2}$ ......... ......... for $k=n-1$ $(u_2-u_1) v_{n-2}=(v_n-v_{n-1}) u_0$ Now if we sum them we will get $u_n=v_n$ My friend what a beautiful solution!!!!I would give a special prize for this!!

Remark: If $a_i = 1$ for all $i$, then $u_n = F_{n+1}$, the $(n+1)^{th}$ Fibonacci number. For this case, the final expression for $u_n$ in djmathman's solution counts $F_{n+1}$ in a nice way- Using the tiling interpretation of $F_{n+1}$, each term in the expression corresponds to exactly one way of tiling a $1 * n$ boards using squares and dominoes by the following bijection: For the term $a_i*a_j*...*a_k$, the corresponding tiling has dominoes placed at exactly the $i^{th}, j^{th}, ..., k^{th}$ cells. As each term equals $1$ if all $a_i$ equal $1$, the whole expression indeed evaluates to $F_{n+1}$.

Does this work? We proceed by induction, with any base cases being easily checked. For any sequence of real numbers $x_1,x_2,\dots$ recursively define \[f(x_1)=1+x_1,\ f(x_2)=1+x_1+x_2\]\[f(x_1,\dots,x_k)=f(x_1,\dots,x_{k-1})+x_kf(x_1,\dots,x_{k-2})\]so that for $k\ge 2$, \[u_k=f(a_1,\dots,a_{k-1})\]\[v_k=f(a_{n-1},\dots,a_{n-k+1})\]for convenience, let $g(i,j)=f(a_i,\dots,a_j)$ (where the sequence goes $a_i,a_{i+1},\dots,a_j$ if $i<j$ and goes $a_i,a_{i-1},\dots,a_j$ if $i>j$). By induction, we know that $g(i,j)=g(j,i)$ for any $|i-j|\le n-3$. We want to prove that \[g(1,n-1)=g(n-1,1)=g(n-1,2)+a_1g(n-1,3)=g(2,n-1)+a_1g(3,n-1)\]However, note that this must be true if we replace $n-1$ with anything less, therefore \[g(1,n-2)=g(2,n-2)+a_1g(3,n-2)\]\[a_{n-1}g(1,n-3)=a_{n-1}(g(2,n-3)+a_1g(3,n-3))\]Adding the two equations up, we get our desired result.

As v_Enhance mentioned, it suffices to solve the problem in the special case where $a_k$ are positive integers. Consider $n-1$ boxes placed on a line in the following order: $B_1,B_2,\ldots ,B_{n-1}$. Place $a_k$ balls in the box $B_k$. Claim. $u_{k+1}$ is the number of ways of choosing some balls from the first $k$ boxes such that from every box, we choose at most one ball, and we don't choose two balls from consecutive boxes (also counting not choosing any ball). We proceed using induction. The base cases $k=0$ and $k=1$ are trivial as $u_1=1$ and $u_2=a_1+1$. Suppose that the claim is true for $k-1$ and $k$. We'll prove that the claim also holds for $k+1$. If we don't choose any balls from $B_k$, then there are $u_k$ ways of choosing the balls. If we choose one ball from $B_k$, then there are $a_ku_{k-1}$ ways of choosing the balls. Since $u_{k+1} = u_k + a_k u_{k-1}$, the claim holds for all $0\le k\le n$. In a similar manner, one can prove that $v_{k+1}$ is the number of ways of choosing some balls from the last $k$ boxes such that from every box, we choose at most one ball, and we don't choose two balls from consecutive boxes (also counting not choosing any ball). The conclusion follows.

My Proof is written by me: You can REEEEwrite this problem in terms of setz. DEFINITION: $U_0 = U_1 = V_0 = V_1 = \{ 1 \}, U_k = U_{k - 1} \cup a_{k}U_{k - 2}$ and $V_k = V_{k - 1} \cup a_{n - k}V_{k - 2}$ where $a_1, a_2, ... a_n$ are real numbers. Where $bC = \{ bc | c \in C \}$ for some $b \in \mathbb{R}$ This set notation gives us two useful properties: $U_0 \subset U_1 \subset U_2 \subset .... \subset U_n$ and $\sum_{r \in U_k} r = u_k$. Also, every term in $U_k$ is of the form $a_{n - e_1}a_{n - e_2}...a_{n - e_l}$ where $e_1, ... , e_n$ are integers. We need to prove that $U_n = V_n$ Claim 1: none of the integers in $e_1,...,e_n$ can be consecutive: PROOF: Suppose that $e_{t+1} = e_t + 1$. The only time $a_{e_{t+1}}$ is introduced in this product is when we evaluate $a_{e_{t+1}}U_{e_{t+1} - 2}$. However since $e_t < e_{t+1}$, we must have $a_{e_t} \in U_{e_{t+1} - 2}$ which is impossible since $e_t > e_{t+1} - 2$ $\therefore$ none of the integers can be consecutive Claim 2: $V_k = \{ a_{n - e_1}a_{n - e_2}...a_{n - e_l} | a_{e_1}a_{e_2}...a_{e_l} \in U_k\}$ (basically the result formed when replacing every occurance of $a_i$ in $U_k$ with $a_{n - i}$ for all $i \leq k$ is equal to $V_k$). Let $S_k$ be the set when you've applied the index thingy to $U_k$ This will be proved with induction on k: BASE CASE: $U_1 = \{ 1, a_1\}, V_1 = \{ 1, a_{n-1} \}$ $1$ becomes $1$ and $a_1$ becomes $a_{n - 1} \implies S_1 = \{ 1, a_{n - 1} \} = V_1$ So the base case is proved. Suppose that all $m \leq w$ satisfy the claim. Consider m = w + 1: since $U_{w + 1} = U_w \cup a_{w + 1}U_{w - 1}$, we can consider what $U_w$ and $a_kU_{w - 1}$ turn into $U_w$ turns into $S_w = V_w$ and $a_{w + 1}U_{w - 1}$ turns into $a_{n - w - 1}S_{w - 1} = a_{n - w - 1}V_{w - 1}$ by the inductive argument. $\implies S_{w+1} = V_w \cup a_{n - w - 1}V_{w - 1} = V_{w+1}$ $\therefore$ the claim is proved by induction Using the claim above, it can be seen that in order to have $U_n = V_n$, we need to prove that if $a_{e_1}a_{e_2}...a_{e_l} \in U_n$, then $a_{n - e_1}a_{n - e_2}...a_{n - e_l} \in U_n$: PROOF: WLOG we have $e_1 < e_2 < ... < e_l \iff n - e_1 > n - e_2 > ... > n - e_l$ $a_{n - e_l} \in U_{n - e_l}$ and $U_{n - e_l} \subseteq U_{n - e_{l-1} - 2}$ because if $n - e_l = n - e_{l - 1} - 1$, then $e_l$ and $e_{l - 1}$ are consectuve which contradicts claim 1. $\implies a_{n - e_l}a_{n - e_{l - 1}} \in a_{e_{l - 1}}U_{n - e_{l-1} - 2} \implies a_{n - e_l}a_{n - a_{l - 1}} \in U_{n - e_{l - 1}}$. Repeating this logic with $a_{n - e_l}a_{n - e_{l - 1}}$ and $a_{n - e_{l - 2}}$, we get that $a_{n - e_l}a_{n - e_{l - 1}}a_{n - e_{l - 2}} \in U_{n - e_{l - 2}}$. After going through all the terms in the initial product, we get that $a_{n - e_1}a_{n - e_2}...a_{n - e_l} \in U_{n - e_1} \subset U_n$ $\therefore U_n = V_n \implies u_n = v_n$

Laziness does pay off sometimes . (My main (non)motivation for the problem was to get rid of the $a_i$s, so that what remains is just plain manipulation) Problem translates to: Given $u_0 = u_1 = v_0 = v_1 = 1$ and that- $$\frac{u_{k+1} - u_k} {u_{k-1}} = \frac{v_{n-(k-1)} - v_{n-k} }{v_{n-(k+1)}}$$for $k =1, \ldots, n-1.$ Prove that $u_n = v_n.$ The problem statement translates to : $$v_{n-(k-1)}u_{k-1} - v_{n-k}u_{k-1} = u_{k+1}v_{n-(k-1)} - u_kv_{n-(k-1)}$$ Now, writing all the $(n-1)$ equations, we have- $v_nu_0 - v_{n-1}u_0 = u_2v_{n-2} - u_1v_{n-2}$ $v_{n-1}u_1 - v_{n-2}u_1 = u_3v_{n-3} - u_2v_{n-3}$ $v_{n-2}u_2 - v_{n-3}u_2 = u_4v_{n-4} - u_3v_{n-4}$ $v_{n-3}u_3 - v_{n-4}u_3 = u_5v_{n-5} - u_4v_{n-5}$ $\vdots$ $v_2u_{n-2}-v_1u_{n-2} = u_nv_0-u_{n-1}v_0$ And these nicely add up to give us $\boxed{u_n = v_n}$.

Solution using linear algebra: Let $A_i = \begin{bmatrix}0 & 1 \\ a_i & 1\end{bmatrix}$, then it suffices for us to prove that $$\begin{bmatrix}0 & 1\end{bmatrix} A_{n-1}A_{n-2}\dots A_1\begin{bmatrix}1 \\ 1\end{bmatrix} = \begin{bmatrix}0 & 1\end{bmatrix} A_1A_2\dots A_{n-1}\begin{bmatrix}1 \\ 1\end{bmatrix}.$$Define a linear transformation $f: \text{M}(2,\mathbb{C}) \to \text{M}(2,\mathbb{C})$ by $$f(M) = XM^{\text{T}}X^{-1},\ X=\begin{bmatrix}0 & \text{i} \\ \text{i} & \text{i}\end{bmatrix}.$$Then one can verify that $f(A_i) = A_i$, so $$f(A_{n-1}A_{n-2}\dots A_1) = A_1A_2\dots A_{n-1}.$$Also we have $$\begin{bmatrix}0 & 1\end{bmatrix} M \begin{bmatrix}1 \\ 1\end{bmatrix} = \begin{bmatrix}0 & 1\end{bmatrix} f(M)\begin{bmatrix}1 \\ 1\end{bmatrix}$$for any 2 by 2 matrix $M$, so we are done.

lyukhson wrote: Let $n$ be a positive integer and let $a_1, \ldots, a_{n-1} $ be arbitrary real numbers. Define the sequences $u_0, \ldots, u_n $ and $v_0, \ldots, v_n $ inductively by $u_0 = u_1 = v_0 = v_1 = 1$, and $u_{k+1} = u_k + a_k u_{k-1}$, $v_{k+1} = v_k + a_{n-k} v_{k-1}$ for $k=1, \ldots, n-1.$ Prove that $u_n = v_n.$ The following claim kills the problem. Let the empty product be $1$ as usual. Define the set $S_n$ to be the set of all subsets $A$ of $\{1,\dots , n\}$ such that no two elements $a,b\in A$ satisfy $|a-b|=1$. Claim: We have $u_k = \sum_{A\in S_{k-1}} \prod_{i \in A} a_i$ for all $1\le k \le n$. Solution: We use induction. The base case is trivial. Induction Step: Expand $u_{k+1}=u_k+a_ku_{k-1}$ with the inductive hypothesis and remark that each set $A\in S_k$ is represented by exactly one instance of $\prod_{i\in A}a_i$. $\fbox{}$ Now, note that this claim for $k=n$ gives that $u_n=\sum_{A\in S_{n-1}} \prod_{i\in A} a_i$. However, similarly we have $v_n = \sum_{A\in S_{n-1}} \prod_{i\in A} a_{n-i}$. Remark that both sums are the same to finish.

We fully classify the sequence $u_n$. Claim: Let $T_n$ be the set of all subsets of $\{1,\ldots,n\}$ such that no two elements of the subset differ by 1. Then $u_{n+1}=\displaystyle \sum_{S\in T_n} \displaystyle \prod_{i\in S} a_i$. Proof: Induct on $n$, base case $n=1$ clear. We can build $T_n$ from $T_{n-1},T_{n-2}$ as follows. To get the subsets of $T_n$ that contain $n$, simply tack on $n$ to all elements of $T_{n-2}$. The set of subsets of $T_n$ that do not contain $n$ is simply $T_{n-1}$. Since $u_{n+1} = u_n+a_nu_{n-1}$, this algebraically encodes exactly what we need, proving the induction. $\blacksquare$ Define the opposite of a set $S$ to be $\{n-a: a\in S\}$. Now, simply note that replacing each element $S\in T_n$ with its opposite does not change $T_n$. Therefore, $u_n=v_n$.

We have $u_{k + 1} = u_{k} + a_{k}\cdot u_{k - 1}$ and $v_{n - k + 1} = v_{n - k} + a_{k}\cdot v_{n - k - 1}$, which are equivalent with $u_{k + 1} - u_{k} = a_{k}\cdot u_{k - 1}$ and $v_{n - k + 1} - v_{n - k} = a_{k}\cdot v_{n - k - 1}$, respectively, which imply $v_{n - k - 1}\cdot(u_{k + 1} - u_{k}) = a_{k}\cdot v_{n - k - 1}\cdot u_{k - 1} = u_{k - 1}\cdot (v_{n - k + 1} - v_{n - k})$ for $k = 1, ..., n - 1$. Summing all these equalities for $k = 1, ..., n - 1$ and cancelling equal terms yields $u_{0}\cdot v_{n} - u_{0}\cdot v_{n - 1} + u_{1}\cdot v_{n - 1} = u_{n - 1}\cdot v_{1} + u_{n}\cdot v_{0} - u_{n - 1}\cdot v_{0}$, and since $u_{0} = u_{1} = v_{0} = v_{1} = 1$, we get $u_{n} = v_{n}$, as desired.

We treat $(a_i)$ as a sequence of variables, and $u_i(a_1,a_2,...a_{i-1})$ as a sequence of functions on these variables. Now, for a function $f(a_1,a_2,...a_{i-1})$, we define $\Pi_k(f)=f(a_{k-1},a_{k-2},...,a_{k-i+1})$ for $k\geq i$, and define $\Theta_k(f)=f(a_{1+k},a_{2+k},...,a_{i-1+k})$ for $k\in \{1,2\}$, where $a_{n+1}$ is an arbitrary real number. Note that: $$\Theta_k(f)\Theta_k(g)=\Theta_k(fg)$$$$\Theta_k(f)+\Theta_k(g)=\Theta_k(f+g)$$$$\Pi_k(f)\Pi_k(g)=\Pi_k(fg)$$$$\Pi_k(f)+\Pi_k(g)=\Pi_k(f+g)$$ Then, we have that $u_i=\Pi_n(v_i)$. We now claim that $u_i=\Pi_i(u_i)$ For the proof, we first prove by induction that $u_{k+1}=\Theta_1(u_{k})+a_1\Theta_2(u_{k-1})$. The base case $k=1$ is trivial, so $$\iff \Theta_1(u_{k})+a_1\Theta_2(u_{k-1})=u_{k}+a_ku_{k-1}=\Theta_1(u_{k-1})+a_1\Theta_2(u_{k-2})+a_k\Theta_1(u_{k-2})+a_1a_k\Theta_2(u_{k-3})$$$$\iff \Theta_1(u_{k})+a_1\Theta_2(u_{k-1})=\Theta_1(u_{k-1})+a_1\Theta_2(u_{k-2})+\Theta_1(a_{k-1}u_{k-2})+a_1\Theta_2(a_{k-2}u_{k-3})$$Wich is true by the linearity of $\Theta_k$. Now, suppose, for induction that $u_i=\Pi_i(u_i)$ for $i<n$ But note that $$\Pi_n(u_n)=\Pi_n(u_{n-1})+\Pi_n(a_{n-1}u_{n-2})=\Theta_1(\Pi_{n-1}(u_{n-1}))+\Theta_2(a_1\Pi_{n-2}(u_{n-2})$$$\implies \Pi_n(u_n)=\Theta_1(u_{n-1})+\Theta_2(a_1u_{n-2})=u_n$. Hence, $u_n=v_n \blacksquare$

When we start expanding, we get that: $$u_n = 1+\sum_{t=1}^{n-1} a_t + \sum_{c_1=1}^{n-1} a_{c_1}\left(\sum_{c_2 \geq c_1 + 2} a_{c_2} + \sum_{c_2 \geq c_1+2} a_{c_2} \sum_{c_3 \geq c_1+4} a_{c_3}+\dots+\underbrace{\sum_{c_2 \geq c_1+2}a_{c_2} \sum_{c_3 \geq c_1+4}a_{c_3} \dots \sum_{c_{t-1} \geq 2+2(t-1)} a_{c_{t-1}}}_{t-1 \; \text{sums}}\right)$$where $t = \left \lfloor \frac{n}{2} \right \rfloor$. Now to get $v_n$ we do the same expanding we have done for $u_n$ and we notice that the indices they are going just to going to be $n$ minus that index. In other words we are going to have indices of the value $n-c_1$, $n-c_2$, $n-c_3$, etc. Then we notice that we can rearrange the elements inside the bracket to get that $u_n=v_n$.

We note that this is equivalent to showing that $u_n$ has terms which are symmetric about the index of $\frac{n}{2}$. Let $S_n$ be the set of subsets of $\{1,2,\ldots n-1\}$ where no two elements differ by 1. I claim that $u_n$ can be written as \[u_n =\sum_{i\in S} a_i\] We prove this with induction. The base cases are trivial for $n=0,1$. Now for the inductive step. We have that \[u_{k+1} = u_k+a_k \cdot u_{k-1} = \sum_{i\in (S_k \cup \{S_{k-1}+a_k\})}a_i = \sum_{i\in S_{k+1}} a_i\]where the last equality is true because each element of $S_{k+1}$ either contains or does not contain $a_k$. Thus our induction is complete, and we have shown that $u_n$ is symmetric, so $u_n=v_n$.

dame dame

We can in fact characterize $u_n$. It is the sum of all products of $a_i$ such that $i \le n-1$ such that no two consecutive indices are in the same product. It's true in the first few cases, $u_2 = a_1 + 1$ and $u_3 = 1 + a_1 + a_2$. Now suppose its true until $n$. Now note since that $u_{n+1} = u_n + a_nu_{n-1}$ and $u_{n-1}$ has $a_i$'s with $i$ at most $n-2$, we still don't have two consecutive indices in a product. To show every such product appears, see that $u_n$ takes care of all things without $a_n$ and $a_n$ can be multiplied by only things at most $a_{n-2}$, so the induction holds. Now, the problem follows since this expression is invariant under replacing $a_i$ with $a_{n-i}$, so $u_n = v_n$ always.

ISL marabot solve Look at the first few terms of $u_k$. We have $u_0=1 \\ u_1=1 \\ u_2=a_1+1 \\ u_3=1+a_1+a_2 \\ u_4=1+a_1+a_2+a_1a_3+a_3 \\ u_5=1+a_1+a_2+a_1a_3+a_3+a_4+a_1a_4+a_2a_4$ We see a pattern. Claim: $u_k$ is the sum of $1$ and all the products of $a_{i_1}\cdot a_{i_2}\cdot a_{i_3}\cdots$, where $i_1, i_2, i_3, \ldots$ are positive integers less than $k$ so that no two are consecutive. Proof: We proceed by induction on $k$. Base cases above. Note: covers means is the sum of Inductive step: Suppose it's true for $k-1$. Then note $u_{k-1}$ covers all these such products that don't involve $a_{k-1}$. We have $u_{k}=u_{k-1}+a_{k-1}\cdot u_{k-2}$. Note $u_{k-2}$ covers all these such products that don't involve $a_{k-1}$ or $a_{k-2}$. Since no such product involves $a_{k-1}$ and $a_{k-2}$, $a_{k-1}\cdot u_{k-2}$ covers all such products that involve $a_{k-1}$. Thus, $u_k$ covers all such products, and the induction is complete. Now we will characterize $v_k$. Note that by induction on $k$ in a similar fashion to $u_k$, we find $v_k$ is the sum of $1$ and all the products of $a_{n-j_1}\cdot a_{n-j_2}\cdot a_{n-j_3}\cdots$, where $j_1, j_2, j_3, \ldots$ are positive integers less than $k$ so that no two are consecutive. Note that if a product is included in $u_n$, then it is also included in $v_n$ and that the converse is also true (since $i_1$ can be written as $n-j_1$ for some positive integer $j_1$, and $n-j_1$ can be written as $i_1$ for some positive integer $i_1$). Since $1$ is included in both of them, $u_n=v_n$.

lyukhson wrote: Let $n$ be a positive integer and let $a_1, \ldots, a_{n-1} $ be arbitrary real numbers. Define the sequences $u_0, \ldots, u_n $ and $v_0, \ldots, v_n $ inductively by $u_0 = u_1 = v_0 = v_1 = 1$, and $u_{k+1} = u_k + a_k u_{k-1}$, $v_{k+1} = v_k + a_{n-k} v_{k-1}$ for $k=1, \ldots, n-1.$ Prove that $u_n = v_n.$ $$a_k=\frac{u_{k+1}-u_k}{u_{k-1}}=\frac{v_{n-k+1}-v_{n-k}}{v_{n-k-1}}$$$$u_{k+1} \cdot v_{n-k-1} - u_k \cdot v_{n-k-1} = u_{k-1} \cdot v_{n-k+1} - u_{k-1} \cdot v_{n-k} $$$$u_{k+1} \cdot v_{n-k-1} - u_{k-1} \cdot v_{n-k+1} = u_k \cdot v_{n-k-1} - u_{k-1} \cdot v_{n-k} $$$$\sum u_{k+1} \cdot v_{n-k-1} - \sum u_{k-1} \cdot v_{n-k+1} = \sum u_k \cdot v_{n-k-1} -\sum u_{k-1} \cdot v_{n-k} $$$$u_{n-1} + u_n -v_n -v_{n-1} = u_{n-1} -v_{n-1}$$$$u_n =v_n$$

solution sketch: consider subset of $\{a_1,a_2,a_3,\dots,a_{i-1}\}$ without any consecutive elements, that is, $a_j,a_{j+1}$ and consider the product of all elements in that subset. $u_i$ will be product of all such subsets. proof by induction. analogous holds for $v$ and $u_n=v_n$ follows.

It suffices to show that all $u_i$ for $0\le i\le n$ are symmetric; that is, if $a_{n_1}a_{n_2}\dots a_{n_k}$ is a summand in $u_i$, it suffices to show that $a_{i+1-n_1}a_{i+1-n_2}\dots a_{i+1-n_k}$ is as well. I claim that for all terms in each $u_i$ for $0\le i\le n$, none of them have a coefficient which is greater than $1$. We show this by induction. The base cases $u_0$ and $u_1$ are trivial. Now clearly $a_iu_{i-1}$ and $u_i$ don't share any like terms, since none of the terms in $u_i$ are divisible by $a_i$. But by the inductive hypothesis, the summands themselves don't have like terms, so the induction is complete. Now for each $u_i$ assign to it a group of sets $S_i$ such that the set $\{n_1,n_2,\dots,n_k\}$ is contained in $S_i$ if and only if the term $a_{n_1}a_{n_2}\dots a_{n_k}$ is a summand in $u_i$ (we let the empty set represent $1$). Then I claim that the number of sets in $S_i$ of size $k$ (where $k\le \frac{i+1}{2}$) is precisely $\binom{i-k+1}{k}$. Again, we show this by induction. The base cases $i=0$ and $i=1$ are trivial. The number of sets in $S_i$ of size $k$ is equal to the number of sets in $S_{i-1}$ of size $k$ plus the number of sets in $S_{i-2}$ of size $k-1$. When $i$ is odd and $k=\frac{i+1}{2}$, there are $0$ sets in $S_{i-1}$ of size $k$ and $1$ set in $S_{i-2}$ of size $k-1$ by the inductive hypothesis. Otherwise, we can simply note that \[\binom{i-k}{k-1}+\binom{i-k}{k}=\binom{i-k+1}{k}\]which completes the induction. Finally, I claim that no set of $S_i$ can contain two consecutive numbers. We again show this by induction (for the third time). Note that $S_i$ consists of all the sets from $S_{i-1}$ as well as all the sets from $S_{i-2}$ but with the number $i$ appended to each set. Then by the inductive hypothesis it is clear that $S_i$ cannot contain two consecutive numbers. Note that by stars and bars there are precisely $\binom{i-k+1}{k}$ possible sets containing only numbers from $1$ to $i$ which have size $k$ and contain no two consecutive numbers. Since there were also $\binom{i-k+1}{k}$ possible sets of size $k$ in $S_i$, it follows that a set is in $S_i$ if and only if it contains only numbers from $1$ to $i$ and also does not contain any two consecutive elements. At this point, the conclusion easily follows: it suffices to show that if $\{n_1, n_2, \dots, n_k\}$ is in $S_i$, then $\{i+1-n_1, i+1-n_2, \dots, i+1-n_k\}$ is as well, which is true. $\blacksquare$

Nice Consider good subsets of $\{a_1,a_2,a_3,\dots,a_{i-1}\}$, subsets without any consecutive elements, that is, $a_j,a_{j+1}$ and consider the product of all elements in that subset. We claim that $u_i$ will be product of all such subsets. Then, the analogous would hold for $v$ and $u_n=v_n$ follows. We prove our claim with induction. The claim is trivially true for $i=0,1.$ Suppose it's true for $i-1,i$ we will prove it for $i+1.$ Now, $u_{i+1}=u_i+a_ku_{i-1}$ so for every good subset $S$ of $\{a_1,a_2,a_3,\dots,a_{i}\}$, if it contains $a_i$ then it cannot contain $a_{i-1}$ so $S\setminus a_{i}$ will be a good subset of $\{a_1,a_2,a_3,\dots,a_{i-2}\}.$ On the other hand, if it doesn't contain $a_i$ then it will just be a good subset of $\{a_1,a_2,a_3,\dots,a_{i-1}\}.$ Thus, the claim is proved.

Let $S_m$ be the set of subsets of $\{a_1,a_2,a_3, \dots , a_{m-1} \}$ with no consecutive elements. We claim $u_k=\sum_{S \in S_{k-1}} \prod_{s \in S} a_s$, and a similar argument gives $u_n=v_n$. We prove this by induction on $k$ with the base case $u_0=u_1=1$ being obvious. We have that $$u_{k+1}=u_k+a_ku_{k-1} = \sum_{S \in S_{k} \text{ without } a_k} \prod_{s \in S} a_s + \sum_{S \in S_{k} \text{ with } a_k} \prod_{s \in S} a_s = \sum_{S \in S_{k}} \prod_{s \in S} a_s,$$as desired so we are done.

ISL Marabot solve Let, $S_k$ be the set of all subsets $X$ of $\{1,2,\dots, k\}$ such that, $x\in X \implies x+1 \notin X$. Clearly, $$S_x = S_{x-1} \cup \{X\cup\{x\}:X\in S_{x-2}\} \qquad (1)$$ $\boxed{\textbf{Claim: } u_{x+1} = \sum\limits_{X\subseteq S_x} \left(\prod\limits_{i\in X}a_i\right)}$ $\textbf{Proof: }$ We can prove this by induction. We can easily show the base cases, $u_2=a_1+1$, $u_3=a_2+a_1+1$ and $u_4=a_1a_3+a_1+a_2+a_3+1$. Now, lets assume that it is true for all $x < k$. So, for $x=k$ we have, \begin{align*} u_{k+1} &= u_k+a_ku_{k-1} \\ &= \sum\limits_{X\subseteq S_{k-1}} \left(\prod\limits_{i\in X}a_i\right) + a_k\sum\limits_{X\subseteq S_{k-2}} \left(\prod\limits_{i\in X}a_i\right) \\ &= \sum\limits_{X\subseteq S_{k-1}} \left(\prod\limits_{i\in X}a_i\right) + \sum\limits_{X\subseteq S_{k-2}} \left(a_k\prod\limits_{i\in X}a_i\right) \\ &= \sum\limits_{X\subseteq S_{k-1}} \left(\prod\limits_{i\in X}a_i\right) + \sum\limits_{X\subseteq S_{k-2}} \left(\prod\limits_{i\in X\cup \{k\}}a_i\right) \\ &= \sum\limits_{X\subseteq S_{k}} \left(\prod\limits_{i\in X}a_i\right) [\text{Using } (1)] \end{align*}So, $u_n =\displaystyle\sum\limits_{X\subseteq S_{n-1}} \left(\prod\limits_{i\in X}a_i\right)$ And now it's trivial that this sum will remain same if we reverse the sequence $(a)_{i=1}^{n-1}$. Therefore, $v_n=\displaystyle\sum\limits_{X\subseteq S_{n-1}} \left(\prod\limits_{i\in X}a_i\right)$ and we are done. $\blacksquare$

Fun fact: this problem arises in the study of simple continued fraction expansions. Given a sequence $a_1,a_2,\ldots$, write \[ \frac{p_n}{q_n} = a_1 + \cfrac{1}{a_2 + \cfrac{1}{\cdots + \cfrac{1}{a_{n-1} + \cfrac 1{a_n}}}}. \]By induction, one can show that the sequence $\{p_n\}_{n\geq 1}$ satisfies the relation $p_{n+1} = p_n + a_np_{n-1}$, which is precisely the recurrence in the problem statement. Reframed in these terms, this problem asks to show that the numerators of \[ a_1 + \cfrac{1}{a_2 + \cfrac{1}{\cdots + \cfrac{1}{a_{n-1} + \cfrac 1{a_n}}}}\quad\text{and}\quad a_n + \cfrac{1}{a_{n-1} + \cfrac{1}{\cdots + \cfrac{1}{a_2 + \cfrac 1{a_1}}}} \]are equal when written as fractions in lowest terms. This is known in the literature; see e.g. Theorem 2 here. (In fact, the proof given in those notes is essentially the same as the proof I posted here eight years ago, and now Dr. Reznick is my advisor!)

Consider $u_n$ and $v_n$ as multilinear functionals. The combinatorial interpretation of the summands is a bijection to a 1x1 and 1x2 domino tiling of a 1xn rectangle. It doesn't matter if you tile from left to right or right to left, so you are done.

Denote $A_s$ as the set of subsets of $\{1,2\cdots s\}$ that does not contain two consecutive positive integers. Similarly, denote $B_s$ as the set of subsets of $\{n-s,n-s+2\cdots n-1\}$ that does not contain two consecutive positive integers. We claim that $$u_k = \sum_{x\in A_{k-1}}\prod_{y\in x}a_y.$$We will use induction. For $k=2,3$ this is true since $u_2=1+a_1$ and $u_3=1+a_1+a_2$. Now, assume that this is true for $k-1$ and $k$. Consider which terms are present in $u_{k+1}$. We copy down the terms from $u_k$, and then put the terms from $u_{k-1}$ but all multiplied by $a_k.$ Note that when constructing the subsets of 1 through $k$ that does not contain two consecutive elements, what we do is take all the valid subsets of 1 through $k-1$, copy them over, and add all the valid subsets of 1 through $k-2$ but with $k$ appended on to it. This is exactly the same as what we are doing to find $u_{k+1}$, so we have shown the claim by induction. Similarly, we can also get that $$v_k = \sum_{x\in B_{k-1}}\prod_{y\in x}a_y.$$ Since $A_{n-1}=B_{n-1}$, from these, we then get that $$u_n=v_n=\sum_{x\in A_{n-1}}\prod_{y\in x}a_y,$$so we are done.

sman96 wrote: ISL Marabot solve Let, $S_k$ be the set of all subsets $X$ of $\{1,2,\dots, k\}$ such that, $x\in X \implies x+1 \notin X$. Clearly, $$S_x = S_{x-1} \cup \{X\cup\{x\}:X\in S_{x-2}\} \qquad (1)$$ $\boxed{\textbf{Claim: } u_{x+1} = \sum\limits_{X\subseteq S_x} \left(\prod\limits_{i\in X}a_i\right)}$ $\textbf{Proof: }$ We can prove this by induction. We can easily show the base cases, $u_2=a_1+1$, $u_3=a_2+a_1+1$ and $u_4=a_1a_3+a_1+a_2+a_3+1$. Now, lets assume that it is true for all $x < k$. So, for $x=k$ we have, \begin{align*} u_{k+1} &= u_k+a_ku_{k-1} \\ &= \sum\limits_{X\subseteq S_{k-1}} \left(\prod\limits_{i\in X}a_i\right) + a_k\sum\limits_{X\subseteq S_{k-2}} \left(\prod\limits_{i\in X}a_i\right) \\ &= \sum\limits_{X\subseteq S_{k-1}} \left(\prod\limits_{i\in X}a_i\right) + \sum\limits_{X\subseteq S_{k-2}} \left(a_k\prod\limits_{i\in X}a_i\right) \\ &= \sum\limits_{X\subseteq S_{k-1}} \left(\prod\limits_{i\in X}a_i\right) + \sum\limits_{X\subseteq S_{k-2}} \left(\prod\limits_{i\in X\cup \{k\}}a_i\right) \\ &= \sum\limits_{X\subseteq S_{k}} \left(\prod\limits_{i\in X}a_i\right) [\text{Using } (1)] \end{align*}So, $u_n =\displaystyle\sum\limits_{X\subseteq S_{n-1}} \left(\prod\limits_{i\in X}a_i\right)$ And now it's trivial that this sum will remain same if we reverse the sequence $(a)_{i=1}^{n-1}$. Therefore, $v_n=\displaystyle\sum\limits_{X\subseteq S_{n-1}} \left(\prod\limits_{i\in X}a_i\right)$ and we are done. $\blacksquare$ BD TST Perfect Scorer SMA NAHIAN SIR (IMO 2023,2024 GOLD MEDALIST)

This is basically much much easier if you treat $u_i$, and $v_i$ as the terms of a dynamic programming recurrence.

Few observations is that we always have a $1$ in the sum and $a_1+a_2+ \dots +a_{n-1}$ both can be proven inductively. Now we notice that if there is a term in the sum that is $a_{i_1}a_{i_2}\cdots a_{i_k}$ with $i_1 < i_2 < \cdots < i_k$, then $i_2 - i_1 \ge 2$, $i_3 - i_2 \ge 2, \dots i_k - i_{k-1} \ge 2$. To prove this, first assume that this holds for $u_k$ then we will show it also hold for $u_{k+1}$. since $u_{k+1}=u_k+ a_ku_{k-1}$, this means that $u_k$ in which it's terms are $a_1,a_2,\dots,a_{n-2}$ will be multiplied by $a_n$ which preserves our condition. Now we can see that by replacing the terms $a_i$ with $a_{n-i}$ we can see that it will also have $2$ as difference between their indices. which means that the same terms in $u_n$ exist, as required.

I claim that $u_n = \sum_S \prod_{i \in S} a_i $ for $S \subseteq \{1,2, \cdots , n - 1\}$ with $S$ having no two consecutive integers. The finish then immediately follows from symmetry. We prove this by induction. The claim is obviously true for $n = 0,1,2,3$ for which we have $u_i = 1,1, 1 + a_1, 1 + a_1 + a_2$. Claim 1: No term ever has two consecutive or equal indices. Proof: Assume there is a first $u_i$ for which this is possible. This then implies $a_{i - 1}u_{i - 2} + u_{i - 1}$ has a term with two consecutive or equal indices, clearly $u_{i - 1}$ doesn't so it must be $a_{i - 1}u_{i -2}$, but this is also clearly impossible since the highest index of a factor of a term in $u_{i - 2}$ is $a_{i - 3}$. Claim 2: No term has a coefficient greater than $1$. Proof: Assume to the contrary that there exists a first index $i$ such that $u_i$ contains a term with a coefficient greater than $1$. This would imply that $u_{i - 1}, a_{i - 1}u_{i - 2}$ have a common term, but this is impossible since no terms in $u_{i - 1}$ have $a_{i - 1}$, but all the terms in $a_{i - 1}u_{i - 2}$ do. Inductive Step: Given the two previous claims, it suffices just to prove all terms that have no two indices consecutive appear in $u_n$. Proof: This immediately follows from dissecting the set of possible terms with no two indices into two groups, the first having $a_{n - 1}$ and the latter not. The first one is just then $a_{n - 1}u_{n - 2}$ by inductive hypothesis and the second one is also just $u_{i - 1}$ by inductive hypothesis, so all such terms appear.

My motivation was initially to set up a generating function (by making the indices on each side somehow add up to a constant, but that didn't work and I found that summing gave such a simple solution Note that $$\frac{u_{k+1}-u_k}{a_{k-1}} = a_k = \frac{v_{n-k+1}-v_{n-k}}{v_{n-k-1}} \implies u_{k+1}v_{n-k-1}-u_kv_{n-k-1} = v_{n-k+1}u_{k-1}-v_{n-k}u_{k-1}$$for $k=1, 2, \cdots, n-1.$ Adding all of these up yields $$u_n+u_{n-1}-v_{n-1}-v_n=-v_{n-1}+u_{n-1} \implies u_n=v_n.$$QED