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}, A_{n+1} = \begin{pmatrix} A_n & I_{2^n} I_{2^n} & A_n \end{pmatrix} (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.