2025 USA-NA-AIO Round 1, Problem 1, Part 7

AI Olympiads 2025 USA-NA-AIO Round 1
1

Part 7 (10 points, non-coding task)

Use the spectral decomposition result to derive a closed form of F_{n} for any n \in \left\{ 0, 1, \cdots \right\}.

  • Reasoning is required.

  • Your answer shall be written in terms of \lambda_0, \lambda_1, and F_0 and F_1.

2

\color{green}{\text{### WRITE YOUR SOLUTION HERE ###}}

For n \geq 1, we have

\begin{align*} \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} & = \mathbf{A}^{n-1} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \left( \mathbf{Q} \mathbf{\Lambda} \mathbf{Q}^\top \right)^{n-1} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \mathbf{Q} \mathbf{\Lambda}^{n-1} \mathbf{Q}^\top \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} . \end{align*}

Thus, for n \geq 1, we have

\begin{align*} F_n & = \begin{bmatrix} 1 & 0 \end{bmatrix} \mathbf{A} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \begin{bmatrix} 1 & 0 \end{bmatrix} \mathbf{Q} \mathbf{\Lambda}^{n-1} \mathbf{Q}^\top \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} \frac{\lambda_0}{\sqrt{1 + \lambda_0^2}} & \frac{\lambda_1}{\sqrt{1 + \lambda_1^2}} \\ \frac{1}{\sqrt{1 + \lambda_0^2}} & \frac{1}{\sqrt{1 + \lambda_1^2}} \end{bmatrix} \begin{bmatrix} \lambda_0^{n-1} & 0 \\ 0 & \lambda_1^{n-1} \end{bmatrix} \begin{bmatrix} \frac{\lambda_0}{\sqrt{1 + \lambda_0^2}} & \frac{1}{\sqrt{1 + \lambda_0^2}} \\ \frac{\lambda_1}{\sqrt{1 + \lambda_1^2}} & \frac{1}{\sqrt{1 + \lambda_1^2}} \end{bmatrix} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \begin{bmatrix} \frac{\lambda_0}{\sqrt{1 + \lambda_0^2}} & \frac{\lambda_1}{\sqrt{1 + \lambda_1^2}} \end{bmatrix} \begin{bmatrix} \lambda_0^{n-1} & 0 \\ 0 & \lambda_1^{n-1} \end{bmatrix} \begin{bmatrix} \frac{\lambda_0}{\sqrt{1 + \lambda_0^2}} & \frac{1}{\sqrt{1 + \lambda_0^2}} \\ \frac{\lambda_1}{\sqrt{1 + \lambda_1^2}} & \frac{1}{\sqrt{1 + \lambda_1^2}} \end{bmatrix} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \begin{bmatrix} \frac{\lambda_0^n}{\sqrt{1 + \lambda_0^2}} & \frac{\lambda_1^n}{\sqrt{1 + \lambda_1^2}} \end{bmatrix} \begin{bmatrix} \frac{\lambda_0}{\sqrt{1 + \lambda_0^2}} & \frac{1}{\sqrt{1 + \lambda_0^2}} \\ \frac{\lambda_1}{\sqrt{1 + \lambda_1^2}} & \frac{1}{\sqrt{1 + \lambda_1^2}} \end{bmatrix} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \begin{bmatrix} \frac{\lambda_0^{n+1}}{1 + \lambda_0^2} + \frac{\lambda_1^{n+1}}{1 + \lambda_1^2} & \frac{\lambda_0^{n}}{1 + \lambda_0^2} + \frac{\lambda_1^{n}}{1 + \lambda_1^2} \end{bmatrix} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} \\ & = \boxed{\left( \frac{\lambda_0^{n+1}}{1 + \lambda_0^2} + \frac{\lambda_1^{n+1}}{1 + \lambda_1^2} \right) F_1 + \left( \frac{\lambda_0^{n}}{1 + \lambda_0^2} + \frac{\lambda_1^{n}}{1 + \lambda_1^2} \right) F_0} . \end{align*}

For n = 0, we can

\frac{\lambda_0^{0+1}}{1 + \lambda_0^2} + \frac{\lambda_1^{0+1}}{1 + \lambda_1^2} = 0

and

\frac{\lambda_0^{0}}{1 + \lambda_0^2} + \frac{\lambda_1^{0}}{1 + \lambda_1^2} = 1 .

Therefore, the above answer holds for all n \in \left\{ 0, 1, \cdots \right\}.

\color{red}{\text{""" END OF THIS PART """}}