Binary Soup. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (1998 Putnam - A4) 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: A recursively defined sequence divisibility problem. Not too uncommon; we use our usual strategy and apply $ \pmod{11} $ and find the recursive relation $ \pmod{11} $. First define $ B_n $ to be the number of digits in $ A_n $; notice, however, that $ B_n = B_{n-1}+B_{n-2} $ and $ B_1 = B_2 = 1 $, meaning that $ B_n $ is simply the Fibonnaci sequence.

We can see that $ A_n $ is just $ A_{n-1} $ followed by $ B_{n-2} $ zeros and then added to $ A_{n-2} $. Translated into math, this is

$ A_n = 10^{B_{n-2}} A_{n-1}+A_{n-2} $.

But we only care about this $ \pmod{11} $, so

$ A_n \equiv (-1)^{B_{n-2}} A_{n-1}+A_{n-2} \pmod{11} $.

Well let's start writing out terms for $ B_n \pmod{2} $ (since that's all we care about) and $ A_n \pmod{11} $.

$ B_n: 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0 \ldots $

$ A_n: 0, 1, 10, 2, 1, 1, 0, 1, 10, 2, 1, 1 \ldots $

We see that every six, both sequences repeat and since they only depend on the two terms before them, we know they will repeat infinitely. Hence our answers are all positive integers $ n \equiv 1 \pmod{6} $. QED.

--------------------

Comment: This problem really wasn't all that hard for an A4; it only required a little sequence construction to find out what the answer was and a rigorous proof even wouldn't be too much of a challenge. It's a good exercise in converting a word problem to something you can work with mathematically and applying mods effectively.

--------------------

Practice Problem: The Fibonnaci sequence is defined by $ F_0 = F_1 = 1 $ and $ F_n = F_{n-1}+F_{n-2} $ for $ n > 1 $. Prove that if $ a|b $ then $ F_a|F_b $.