Putnam 2013, Problem B-1

For positive integers \( n \), let the numbers \( c(n) \) be determined by the rules \( c(1) = 1 \), \( c(2n) = c(n) \), and \( c(2n+1) = (-1)^n c(n) \). Find the value of
\[
\sum_{n=1}^{2013} c(n) c(n+2).
\]

Solution:
Note that

$$c(2k+1)c(2k+3) = (-1)^k c(k)(-1)^{k+1} c(k+1)$$
$$= -c(k)c(k+1)$$
$$= -c(2k)c(2k+2).$$

It follows that $\sum_{n=2}^{2013} c(n)c(n+2) = \sum_{k=1}^{1006} (c(2k)c(2k+2) + c(2k+1)c(2k+3)) = 0$, and so the desired sum is $c(1)c(3) = -1$.

**Remark:** Karl Mahlburg points out the general formula $c(n) = (-1)^{b_0 b_1 + b_1 b_2 + \cdots + b_{k-1} b_k}$ for $n$ having binary representation $b_k \cdots b_0$.