Cool problem. IMO 2013 A1 I guess

For discussing Olympiad Level Algebra (and Inequality) problems
User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm
Cool problem. IMO 2013 A1 I guess

Unread post by ahmedittihad » Sun Jan 01, 2017 1:35 am

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.$
Frankly, my dear, I don't give a damn.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Cool problem. IMO 2013 A1 I guess

Unread post by Thanic Nur Samin » Sat Jan 14, 2017 1:39 pm

I needlessly overcomplicated the problem :oops: but anyway, my solution involves matrix multiplication.

$$\begin{pmatrix}
1\\0
\end{pmatrix}
=\begin{pmatrix}
u_1\\ u_1-u_0
\end{pmatrix}$$

$$\begin{pmatrix}
u_{k+1}\\u_{k+1}-u_k
\end{pmatrix}
=\begin{pmatrix}
u_k+a_ku_{k-1}\\a_ku_{k-1}
\end{pmatrix}
=\begin{pmatrix}
u_k\\u_k-u_{k-1}
\end{pmatrix}
\begin{pmatrix}
1+a_k & -a_k \\
a_k & -a_k
\end{pmatrix}
$$

$$
\begin{pmatrix}
v_1 & v_0-v_1
\end{pmatrix}
=\begin{pmatrix}
1 & 0
\end{pmatrix}
$$

$$\begin{pmatrix}
v_{k+1} & v_k-v_{k+1}
\end{pmatrix}
=
\begin{pmatrix}
1+a_{n-k} & -a_{n-k} \\
a_{n-k} & -a_{n-k}
\end{pmatrix}

\begin{pmatrix}
v_k & v_{k-1}-v_k
\end{pmatrix}
$$

Let $M_k=\begin{pmatrix}
1+a_k & -a_k \\
a_k & -a_k
\end{pmatrix}$.

$$\begin{pmatrix}
u_n
\end{pmatrix}
=
\begin{pmatrix}
1 & 0
\end{pmatrix}
\begin{pmatrix}
u_n\\u_n-u_{n-1}
\end{pmatrix}

=\begin{pmatrix}
1 & 0
\end{pmatrix}
M_1M_2\ldots M_{n-1}
\begin{pmatrix}
u_1\\u_1-u_0
\end{pmatrix}$$

$$
=\begin{pmatrix}
1 & 0
\end{pmatrix}
M_1M_2\ldots M_{n-1}
\begin{pmatrix}
1\\0
\end{pmatrix}
$$

$$
\begin{pmatrix}
v_n
\end{pmatrix}
=
\begin{pmatrix}
v_n & v_n-v_{n-1}
\end{pmatrix}
\begin{pmatrix}
1\\0
\end{pmatrix}
=
\begin{pmatrix}
v_1 & v_0-v_1
\end{pmatrix}
M_1M_2\ldots M_{n-1}\begin{pmatrix}
1\\0
\end{pmatrix}
$$

$$=\begin{pmatrix}
1 & 0
\end{pmatrix}
M_1M_2\ldots M_{n-1}\begin{pmatrix}
1\\0
\end{pmatrix}$$

And thus $u_n=v_n$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply