Page 1 of 1
Cool problem. IMO 2013 A1 I guess
Posted: Sun Jan 01, 2017 1:35 am
by ahmedittihad
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.$
Re: Cool problem. IMO 2013 A1 I guess
Posted: Sat Jan 14, 2017 1:39 pm
by Thanic Nur Samin
I needlessly overcomplicated the problem
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$.