Recurrences Are Cool. Topic: Probability/S&S. Level: AIME.

Problem: Let $ p_k $ be the probability of choosing a positive integer $ n $ from the interval $ [2^{k-1}, 2^k-1] $ such that the binary representation of $ n $ does not contain three consecutive $ 1 $'s. Evaluate the infinite summation $ p_1+p_2+\cdots $.

Solution: First, let $ S_k $ be the number of positive integers $ n $ in the interval $ [2^{k-1}, 2^k-1] $ that do not contain three consecutive $ 1 $'s in their binary representations - note that it is equivalent to the number of binary strings of length $ k $ starting with a $ 1 $ that satisfy that property. By testing, we have $ S_1 = 1 $, $ S_2 = 2 $, $ S_3 = 3 $, $ S_4 = 6 $, $ S_5 = 11 $, $ S_6 = 20 $. You can construct a certain type of table to make these calculations easier. We notice that the recurrence $ S_{k+3} = S_{k+2}+S_{k+1}+S_k $ seems to hold, so we want to try and prove this.

We categorize the strings of length $ k+3 $ based on the last occurence of $ 0 $. It must either be in the last, second to last, or third to last spots. If it is in the last spot, the string is $ \text{blah}0 $ where $ \text{blah} $ has length $ k+2 $ so there are $ S_{k+2} $ of those. Similarly, the other possibilities are $ \text{blah}01 $ or $ \text{blah}001 $, where the $ \text{blah} $'s have length $ k+1 $ and $ k $, respectively, giving the recurrence. Now it remains to sum it.

We want to evaluate $ \displaystyle \sum_{k=1}^{\infty} p_k = \sum_{k=1}^{\infty} \frac{S_k}{2^{k-1}} $ since there are $ 2^{k-1} $ binary strings of length $ k $ that begin with $ 1 $.

Luckily, we know a cool way to evaluate recurrences over a geometric sequence. Let $ \displaystyle S = \sum_{k=1}^{\infty} \frac{S_k}{2^{k-1}} $. Then

$ \displaystyle 2S = 2S_1+\sum_{k=1}^{\infty} \frac{S_{k+1}}{2^{k-1}} $

$ \displaystyle 4S = 4S_1+2S_2+\sum_{k=1}^{\infty} \frac{S_{k+2}}{2^{k-1}} $

$ \displaystyle 8S = 8S_1+4S_2+2S_3+\sum_{k=1}^{\infty} \frac{S_{k+3}}{2^{k-1}} $.

Notice, now that if we take $ S = 8S-4S-2S-S $ a lot of terms cancel due to the recurrence. In fact, all of the summations do! So

$ \displaystyle S = (8S_1+4S_2+2S_3)-(4S_1+2S_2)-2S_1+ \sum_{k=1}^{\infty} \frac{S_{k+3}-S_{k+2}-S_{k+1}-S_k}{2^{k-1}} $

$ S = 2S_1+2S_2+2S_3 = 12 $.

QED.

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

Comment: Both parts of this problem are pretty classical. The first, finding a recurrence for a string satisfying a certain property, and the second, evaluating an infinite summation of the terms of a sequence divided by a geometric series. These two techniques are very useful, however, in approaching many problems. It would not be fun to solve a problem and get to the last step only to find that you do not know how to evaluate the summation to get the final answer.

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

Practice Problem: Evaluate $ \displaystyle \sum_{k=1}^{\infty} \frac{F_k}{n^k} $, where $ n > 1 $ is a positive integer and $ F_k $ is the Fibonacci sequence (i.e. $ F_0 = F_1 = 1 $ and $ F_{k+1} = F_k+F_{k-1} $ for all positive integers $ k $).