Maths Olympiad Prep

Library / Putnam /10 of 60

Putnam

Algebra Difficulty 7.7 National Olympiad, round 2 Find the answer

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Note that c(2k+1)c(2k+3)=(−1)kc(k)(−1)k+1c(k+1)=−c(k)c(k+1)=−c(2k)c(2k+2).\begin{align*} 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). \end{align*} It follows that ∑n=22013c(n)c(n+2)=∑k=11006(c(2k)c(2k+2)+c(2k+1)c(2k+3))=0\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)=−1c(1)c(3) = -1.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.