IMC 2004 · Problem 6

For $n \ge 0$ define matrices $A_n$ and $B_n$ as follows: $A_0 = B_0 = (1)$ and for every $n > 0$

$$A_n = \begin{pmatrix} A_{n-1} & A_{n-1} \\ A_{n-1} & B_{n-1} \end{pmatrix} \quad \text{and} \quad B_n = \begin{pmatrix} A_{n-1} & A_{n-1} \\ A_{n-1} & 0 \end{pmatrix}.$$

Denote the sum of all elements of a matrix $M$ by $S(M)$. Prove that $S(A_n^{k-1}) = S(A_k^{n-1})$ for every $n, k \ge 1$.