## Tuesday, February 27, 2007

### 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$).

#### 1 comment:

1. n is a positive integer? tsk, tsk, tsk...