Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
• Meta

Recurrences Are Cool. Topic: Probability/S&S. Level: AIME. February 27th, 2007

Problem: Let be the probability of choosing a positive integer from the interval such that the binary representation of does not contain three consecutive ‘s. Evaluate the infinite summation .

Solution: First, let be the number of positive integers in the interval that do not contain three consecutive ‘s in their binary representations – note that it is equivalent to the number of binary strings of length starting with a that satisfy that property. By testing, we have , , , , , . You can construct a certain type of table to make these calculations easier. We notice that the recurrence seems to hold, so we want to try and prove this.

We categorize the strings of length based on the last occurence of . 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 where has length so there are of those. Similarly, the other possibilities are or , where the ‘s have length and , respectively, giving the recurrence. Now it remains to sum it.

We want to evaluate since there are binary strings of length that begin with .

Luckily, we know a cool way to evaluate recurrences over a geometric sequence. Let . Then

.

Notice, now that if we take a lot of terms cancel due to the recurrence. In fact, all of the summations do! So

.

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 , where is a positive integer and is the Fibonacci sequence (i.e. and for all positive integers ).

One Response to “Recurrences Are Cool. Topic: Probability/S&S. Level: AIME.”

1. t0rajir0u Says:

n is a positive integer? tsk, tsk, tsk…