Can we find $F(1) + F(2) + F(3) + \dots + F(100)$?

Can we find $F(1) + F(2) + F(3) + \dots + F(100)$?

Question

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$;

---

1. $28$;

---

1. $64$;

---

1. $81$.

Solution

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\text{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).