The function \(F(k)\) is defined for positive integers by \(F(1)=1\), \(F(2)=1\), \(F(3)=-1\) and by the identities \[F(2k)=F(k), \qquad F(2k+1)=F(k)\] for \(k \ge 2\). The sum \[F(1) + F(2) + F(3) + \dots + F(100)\] equals

  1. \(-15\);

  2. \(28\);

  3. \(64\);

  4. \(81\).

It is easiest here to think of \(F(1)\), \(F(2)\), … as a sequence.

The recursion rules \(F(2k) = F(k)\) and \(F(2k+1) = F(k)\) mean that the \(k\)th value gets repeated at the consecutive positions \(2k\) and \(2k+1\). Given the starting values, this means the values of \(F(k)\), when listed in sequence, are \[1,1,-1,\underbrace{1,1}_{\times 2},\underbrace{-1,-1}_{\times 2}, \underbrace{1,1,1,1}_{\times 4},\underbrace{-1,-1,-1,-1}_{\times 4}, \underbrace{1,1,1,1,1,1,1,1}_{\times 8},-1,-1,\dots\] (where the numbers underneath indicate how many repeated numbers appear in the block).

The strings of \(-1\)s end at positions \(3\), \(7\), \(15\), \(31\), …, so if the first \(3\) or first \(7\) or first \(15\) or … terms are added, the sum will be equal to \(1\), as all \(+1\)s and \(-1\)s will cancel out except the first \(1\).

Continuing in this manner, we find that the sum of the first \(127\) terms is equal to \(1\). The last \(32\) terms, and in particular \(F(101)\) to \(F(127)\), are all \(-1\)s. So \[F(1)+F(2)+F(3)+\dots +F(100)+ \underbrace{F(101) + \dots + F(127)}_{\text{all $-1$s}} = 1\] giving \[F(1)+F(2)+F(3)+\dots +F(100) = 1-(-27)=28.\]

Alternatively, the sum of the first \(63\) terms is \(1\), the next \(32\) terms (up to \(F(95)\)) are \(+1\), and the final \(5\) terms are \(-1\), so the total is \(1+32-5=28\).

Hence the answer is (b).