Putnam 1998, Problem A-4

Let \( A_1 = 0 \) and \( A_2 = 1 \). For \( n > 2 \), the number \( A_n \) is defined by concatenating the decimal expansions of \( A_{n-1} \) and \( A_{n-2} \) from left to right. For example \( A_3 = A_2A_1 = 10 \), \( A_4 = A_3A_2 = 101 \), \( A_5 = A_4A_3 = 10110 \), and so forth. Determine all \( n \) such that 11 divides \( A_n \).

Solution:
The number of digits in the decimal expansion of \( A_n \) is the Fibonacci number \( F_n \), where \( F_1 = 1 \), \( F_2 = 1 \), and \( F_n = F_{n-1} + F_{n-2} \) for \( n > 2 \). It follows that the sequence \( \{A_n\} \), modulo \( 11 \), satisfies the recursion \( A_n = (-1)^{F_{n-2}} A_{n-1} + A_{n-2} \). (Notice that the recursion for \( A_n \) depends only on the value of \( F_{n-2} \) modulo \( 2 \).) Using these recursions, we find that \( A_7 \equiv 0 \) and \( A_8 \equiv 1 \) modulo \( 11 \), and that \( F_7 \equiv 1 \) and \( F_8 \equiv 1 \) modulo \( 2 \). It follows that \( A_n \equiv A_{n+6} \pmod{11} \) for all \( n \geq 1 \). We find that among \( A_1, A_2, A_3, A_4, A_5 \), and \( A_6 \), only \( A_1 \) vanishes modulo \( 11 \). Thus \( 11 \) divides \( A_n \) if and only if \( n = 6k + 1 \) for some nonnegative integer \( k \).