IMC 2004 · Day 2 · P12

The quantity $S(A_n^{k-1})$ has a special combinatorical meaning. Consider an $n \times k$ table filled with 0's and 1's such that no $2 \times 2$ contains only 1's. Denote the number of such fillings by $F_{nk}$. The filling of each row of the table corresponds to some integer ranging from 0 to $2^n - 1$ written in base 2. $F_{nk}$ equals to the number of $k$-tuples of integers such that every two consecutive integers correspond to the filling of $n \times 2$ table without $2 \times 2$ squares filled with 1's.

Consider binary expansions of integers $i$ and $j$: $i_n i_{n-1} \dots i_1$ and $j_n j_{n-1} \dots j_1$. There are two cases:

1. If $i_n j_n = 0$ then $i$ and $j$ can be consecutive iff $i_{n-1} \dots i_1$ and $j_{n-1} \dots j_1$ can be consequtive.

2. If $i_n = j_n = 1$ then $i$ and $j$ can be consecutive iff $i_{n-1} j_{n-1} = 0$ and $i_{n-2} \dots i_1$ and $j_{n-2} \dots j_1$ can be consecutive.

Hence $i$ and $j$ can be consecutive iff $(i+1, j+1)$-th entry of $A_n$ is 1. Denoting this entry by $a_{i,j}$, the sum $S(A_n^{k-1}) = \sum_{i_1=0}^{2^n-1} \dots \sum_{i_k=0}^{2^n-1} a_{i_1 i_2} a_{i_2 i_3} \dots a_{i_{k-1} i_k}$ counts the possible fillings. Therefore $F_{nk} = S(A_n^{k-1})$.

The the obvious statement $F_{nk} = F_{kn}$ completes the proof.