### International Mathematics Competition for University Students

July 31 – August 6 2017, Blagoevgrad, Bulgaria

Home

Ivan is Watching You

Results
Individuals
Teams
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}, \quad 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.