MathDB

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.

Problem Statement