Functions and Sequences Problem 
The function $F(k)$ is defined for positive integers as $F(1) = 1$,
  $F(2) = 1$, $F(3) = -1$ and $F(2k) = F(k)$, $F(2k + 1) = F(k)$ for $k \geq
 2$. Then $$F(1) + F(2) + \dotsb + F(63)$$ equals 
$\begin{array}{lr}
 (\text{A}) & 1 \\
 (\text{B}) & -1 \\
 (\text{C}) & -32 \\ 
 (\text{D}) & 32 \\
\end{array}$

My approach: $F(4)=1$, $F(5)=1$, $F(6)=-1$, $F(7)=-1$ (i.e., all values of $F$ are either $1$ or $-1$). I tried to find a pattern for which $F(x)$ repeats after a certain integer but tried till $F(30)$ and cannot find a solution.  Where am I going wrong?
 A: With induction it can be shown that:$$F(2^k)+\cdots+F(2^{k+1}-1)=0$$
for $k=1,2,\dots$
This because $F(2^1)+F(2^2-1)=F(2)+F(3)=1+(-1)=0$ and:$$F(2^{k+1})+F(2^{k+1}+1)+\cdots+F(2^{k+2}-2)+F(2^{k+2}-1)=2F(2^k)+\cdots+2F(2^{k+1}-1)$$
Then $$F(1)+\cdots+F(63)=F(1)+\sum_{k=1}^5\left[F(2^k)+\cdots+F(2^{k+1}-1)\right]=F(1)=1$$
A: By brute force:
$$F(1)=1$$
$$F(2)=1$$
$$F(3)=-1$$
$$F(4)=F(2)=1$$
$$F(5)=F(2)=1$$
$$F(6)=F(3)=-1$$
$$F(7)=F(3)=-1$$
$$F(8)=F(4)=1$$
$$F(9)=F(4)=1$$
$$F(10)=F(5)=1$$
$$F(11)=F(5)=1$$
$$F(12)=F(6)=-1$$
$$F(13)=F(6)=-1$$
$$F(14)=F(7)=-1$$
$$F(15)=F(7)=-1$$
$$F(16)=F(8)=1$$
$$F(17)=F(8)=1$$
$$F(18)=F(9)=1$$
$$F(19)=F(9)=1$$
$$F(20)=F(10)=1$$
$$F(21)=F(10)=1$$
$$F(22)=F(11)=1$$
$$F(23)=F(11)=1$$
$$F(24)=F(12)=-1$$
$$F(25)=F(12)=-1$$
$$F(26)=F(13)=-1$$
$$F(27)=F(13)=-1$$
$$F(28)=F(14)=-1$$
$$F(29)=F(14)=-1$$
$$F(30)=F(15)=-1$$
$$F(31)=F(15)=-1$$
$$\ldots$$
A pattern emerges:
$$F(1)+F(2)+F(3)+F(4)+F(5)+F(6)+F(7)=1$$
$$F(8)+F(9)+F(10)+F(11)+F(12)+F(13)+F(14)+F(15)=0$$
$$F(16)+F(17)+F(18)+\ldots+F(31)=0$$
$$F(32)+\ldots+F(63)=0$$
Therefore,
$$\sum_{i=1}^{63}{F(i)}=F(1)+F(2)+\ldots+F(63)=1+0+0+0=1.$$
CORRECT ANSWER --- A
A: $$F(n)=\left\{\begin{array}{cc}1,&~~~~2^k-1<n\leq2^k+2^{k-1}\\-1,&~~~~~~~2^k+2^{k-1}<n\leq3+2^{k+1}-1\end{array}\right.~~~~~~k\geq2$$
A: For $k \ge 2$ we have:
\begin{align}
F(2k) &= F(k) \\
F(2k+1) &= F(k)
\end{align}
This means
$$
F(n) = F(\lfloor n / 2 \rfloor) \quad (*)
$$
for $n \ge 4$. 
If we are using base 2 numbers this means we have a word of length $m$ with at least three bits
$$
n = (1 b_{m-1} \dotsb b_2 b_1)_2 \quad (b_i \in \{0, 1\})
$$
and $(*)$ means we can shift right the word (dropping the bit at the end) and keep the value of $F$:
$$
F((1 b_{m-1} \dotsb b_2 b_1)_2)
= F((1 b_{m-1} \dotsb b_2)_2) \quad (m \ge 3)
$$
We repeat until we have less than three bits.
In other words 
\begin{align}
F(n) 
&= F((1 b_{m-1})_2) \\
&=
\begin{cases}
F(3), & \text{for } b_{m-1} = 1 \\
F(2), & \text{for } b_{m-1} = 0
\end{cases}
\\
&=
\begin{cases}
-1, & \text{for } b_{m-1} = 1 \\
+1, & \text{for } b_{m-1} = 0
\end{cases}
\end{align}
for $n\ge 4$.
So
$$
\sum_{k=4}^{63} F(k) = 
F(\underbrace{(100)_2}_4) + F((101)_2) + F((110)_2) + F((111)_2) + \\
F(\underbrace{(1000)_2}_8 + \dotsb + F((1111)_2) + \\
F(\underbrace{(10000)_2}_{16} + \dotsb + F((11111)_2) + \\
F(\underbrace{(100000)_2}_{32} + \dotsb + F((111111)_2) \\
$$
We see that we can group the words by length, and that we have as many words with prefix $10$ as with prefix $11$ in each group, so that their $F$ values sum to zero.
Thus the sought sum reduces to
$$
\sum_{k=1}^{63} = F(1) + F(2) + F(3) = 1 + 1 + (-1) = 1
$$
A: We have $F(1)=1, F(2)=1, F(3)=-1$ and $F(2k)=F(k)$ and $F(2k+1)=F(k)$. 
We have to evaluate $S=\sum_{i=1}^{63}F(i)$
Notice that $S=F(1)+F(2)+F(3) + \sum_{i=2}^{31}[F(2k) + F(2k+1)]$
$\Rightarrow S=F(1)+F(2)+F(3) + \sum_{i=2}^{31}[2F(k)]$
$\Rightarrow S=1+2\sum_{i=2}^{31}F(k)$
$\Rightarrow S=1+2[F(2)+F(3)+\sum_{i=2}^{15}[F(2k)+F(2k+1)]]$
$\Rightarrow S=1+2\sum_{i=2}^{15}[F(2k)+F(2k+1)]$
$\Rightarrow S=1+4\sum_{i=2}^{15}F(k)$
$\Rightarrow S= 1+ 4[F(2)+F(3) + \sum_{i=2}^{7}[F(2k)+ F(2k+1)]]$
$\Rightarrow S = 1+ 8\sum_{i=2}^7 F(k)$
Similarly proceeding, we get 
$\Rightarrow S = 1+ 16\sum_{i=2}^3F(k)$
$\Rightarrow S =1$ 
