Problem (Algebra):
For a positive integer $n$, let $C(n)$ equal the number of pairs of consecutive 1's in the binary representation of $n$. For example, $C(183)=C\left(10110111_{2}\right)=3$. Compute $C(1)+C(2)+$ $C(3)+\cdots+C(256)$.

Solution:
Group values of $n$ according to the number of bits (digits) in their binary representations:

| Bits | $C(n)$ values | Total |
| :---: | :---: | :---: |
| 1 | $C\left(1_{2}\right)=0$ | 0 |
| 2 | $C\left(10_{2}\right)=0$ <br> $C\left(11_{2}\right)=1$ | 1 |
| 3 | $C\left(100_{2}\right)=0$ $C\left(101_{2}\right)=0$ <br> $C\left(110_{2}\right)=1$ $C\left(111_{2}\right)=2$ | 3 |
| 4 | $C\left(1000_{2}\right)=0$ $C\left(1001_{2}\right)=0$ $C\left(1100_{2}\right)=1$ $C\left(1101_{2}\right)=1$ <br> $C\left(1010_{2}\right)=0$ $C\left(1011_{2}\right)=1$ $C\left(1110_{2}\right)=2$ $C\left(1111_{2}\right)=3$ | 8 |

Let $B_{n}$ be the set of $n$-bit integers, and let $c_{n}=\sum_{k \in B_{n}} C(k)$ be the sum of the $C$-values for all $n$-bit integers. Observe that the integers in $B_{n+1}$ can be obtained by appending a 1 or a 0 to the integers in $B_{n}$. Appending a bit does not change the number of consecutive 1's in the previous (left) bits, but each number in $B_{n}$ generates two different numbers in $B_{n+1}$. Thus $c_{n+1}$ equals twice $2 c_{n}$ plus the number of new 11 pairs. Appending a 1 will create a new pair of consecutive 1's in (and only in) numbers that previously terminated in 1. The number of such numbers is half the number of elements in $B_{n}$. Because there are $2^{n-1}$ numbers in $B_{n}$, there are $2^{n-2}$ additional pairs of consecutive 1's among the elements in $B_{n+1}$. Thus for $n \geq 2$, the sequence $\left\{c_{n}\right\}$ satisfies the recurrence relation

$$
c_{n+1}=2 c_{n}+2^{n-2}
$$

(Check: the table shows $c_{3}=3$ and $c_{4}=8$, and $8=2 \cdot 3+2^{3-1}$.) Thus

$$
\begin{aligned}
& c_{5}=2 \cdot c_{4}+2^{4-2}=2 \cdot 8+4=20, \\
& c_{6}=2 \cdot c_{5}+2^{5-2}=2 \cdot 20+8=48, \\
& c_{7}=2 \cdot c_{6}+2^{6-2}=2 \cdot 48+16=112, \text { and } \\
& c_{8}=2 \cdot c_{7}+2^{7-2}=2 \cdot 112+32=256 .
\end{aligned}
$$

Because $C(256)=0$, the desired sum is $c_{1}+c_{2}+c_{3}+c_{4}+c_{5}+c_{6}+c_{7}+c_{8}$, which equals 448 .

Final answer: 448