IMC 2017 · Problem 8

Define the sequence $A_1, A_2, \ldots$ of matrices by the following recurrence:

$$A_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad A_{n+1} = \begin{pmatrix} A_n & I_{2^n} \\ I_{2^n} & A_n \end{pmatrix} \quad (n = 1, 2, \ldots)$$

where $I_m$ is the $m \times m$ identity matrix.

Prove that $A_n$ has $n + 1$ distinct integer eigenvalues $\lambda_0 < \lambda_1 < \ldots < \lambda_n$ with multiplicities $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$, respectively.