Problem: For a positive integer $k$,
let $s(k)$ denote the number of $1$s in the binary representation of $k$.
Prove that for any positive integer $n$,
\[ \sum_{i=1}^{n}(-1)^{s(3i)} > 0. \]

Solution: \paragraph{Solution 1.}
Given a set of positive integers $S$, define
\begin{align*}
  f(S) = \sum_{k\in S}(-1)^{s(k)}.
\end{align*}
We also define
\begin{align*}
  S_{\mathrm{even}} &= \{k\in S \mid k\text{ is even}\} \\
  S_{\mathrm{odd}} &= \{k\in S \mid k\text{ is odd}\}
\end{align*}
and apply functions on sets pointwise, e.g.
\[ \frac{S-1}{2} = \left\{\frac{k-1}{2}\mid k \in S\right\}. \]
The problem follows from the first bullet of the following claim.
\begin{claim*}
  For every positive integer $n$,
  \begin{itemize}
    \item $f(\{3, 6, \dots, 3n\}) > 0$
    \item $f(\{1, 4, \dots, 3n-2\}) < 0$
    \item $f(\{2, 5, \dots, 3n-1\}) \leq 0$
  \end{itemize}
\end{claim*}
\begin{proof}
  Induct on $n$. The base case $n=1$ is easy to check.
  \begin{itemize}
    \item For $S = \{3, 6, \dots, 3n\}$,
    \begin{align*}
      f(S) &= f(S_{\mathrm{even}}) + f(S_{\mathrm{odd}}) \\
      &= f(S_{\mathrm{even}}/2) - f((S_{\mathrm{odd}}-1)/2) > 0
    \end{align*}
    since the elements of $S_{\mathrm{even}}/2$ are $0 \bmod 3$
    and the elements of $(S_{\mathrm{odd}}-1)/2$ are $1 \bmod 3$.

    \item For $S = \{1, 4, \dots, 3n-2\}$,
    \begin{align*}
      f(S) &= f(S_{\mathrm{even}}) + f(S_{\mathrm{odd}}) \\
      &= f(S_{\mathrm{even}}/2) - f((S_{\mathrm{odd}}-1)/2) < 0
    \end{align*}
    since the elements of $S_{\mathrm{even}}/2$ are $2 \bmod 3$
    and the elements of $(S_{\mathrm{odd}}-1)/2$ are $0 \bmod 3$.
    (Note that $(S_{\mathrm{odd}}-1)/2$ has multiples of $3$ starting at $0$ rather than $3$,
    but this is fine because $f(\{3, \dotsc, 3n\}) > 0$ clearly implies $f(\{0, \dotsc, 3n\}) > 0$ as well.)

    \item For $S= \{2, 5, \dots, 3n-1\}$, there are two cases.
    \begin{itemize}
      \item Case 1: $2^{2k-1} \leq 3n-1 < 2^{2k}$. Define
      \begin{align*}
        S_{\mathrm{small}} &= \{s \in S \mid s < 2^{2k-1}\} \\
        S_{\mathrm{big}} &= \{s \in S \mid s \geq 2^{2k-1}\}.
      \end{align*}
      Then
      \begin{align*}
        f(S) &= f(S_{\mathrm{small}}) + f(S_{\mathrm{big}}) \\
        &= f(S_{\mathrm{small}}) - f(S_{\mathrm{big}} - 2^{2k-1}) < 0
      \end{align*}
      since $S_{\mathrm{big}} - 2^{2k-1} = \{0, \dots, 3n-1-2^{2k-1}\}$
      consists of a prefix of the $0\pmod 3$ positive integers in addition to $0$.
      \item Case 2: $2^{2k} < 3n-1 < 2^{2k+1}$.
      Note that if $a+b = 2^{2k+1}-1$, then $f(\{a, b\}) = 0$.
      If we use this to cancel out all pairs of numbers in $S$ which add to $2^{2k+1}-1$,
      then we find
      \[ f(S) = f(\{2, 5, \dots, 2^{2k+1}-3n-2\}) \leq 0. \]
    \end{itemize}
  \end{itemize}
  This completes the induction.
\end{proof}

\paragraph{Solution 2.}
Let
\[ f(n) = \sum_{i=0}^n (-1)^{s(3i)}, \qquad g(n) = \sum_{i=0}^n (-1)^{s(i)}. \]
Note that the problem is equivalent to showing $f(n) \geq 2$ for all $n \geq 1$.

\begin{lemma*}
  $|g(n)| \leq 1$ for all $n$.
\end{lemma*}
\begin{proof}
  Note that $s(2i+1) = -s(2i)$, so $g(2n+1) = 0$ and $g(2n) = (-1)^{s(2n)}$ by pairing terms.
\end{proof}

We will now prove that $f(n)\geq 2$ for all $n\geq 1$ by strong induction.
We can manually verify $n\leq 5$ as a base case.
For the inductive step, let $m = \lfloor\frac{3n-3}{4}\rfloor$ so that $4m+3\leq n$.
Let $S = \{0, 3, \dots, 3n\}$.
Given $0\leq k\leq m$, we can append two digits to the binary representation of $k$
(equivalently, $4k+r$ for $0\leq r < 4$) to get a number in $S$.
If $k$ is a multiple of $3$, we can append $00$ or $11$.
Otherwise, we can append one of $01$ or $10$ depending on $k\pmod{3}$.
Almost all elements of $S$ can be covered uniquely in this way,
except for at most one missing element.
Note that appending $00$ or $11$ will preserve the parity of the number of $1$s
while appending $01$ or $10$ will change the parity. Therefore we can write
\[
  f(n)\geq 2\sum_{\substack{0\leq i\leq m \\ i\equiv 0\pmod{3}}} (-1)^{s(i)}
  - \sum_{\substack{0\leq i\leq m \\ i\not\equiv 0\pmod{3}}} (-1)^{s(i)} - 1\]
(the $-1$ is to account for the possible missing element). Let
\[
  x = \sum_{\substack{0\leq i\leq m \\ i\equiv 0\pmod{3}}} (-1)^{s(i)},
  \qquad y = \sum_{\substack{0\leq i\leq m \\ i\not\equiv 0\pmod{3}}} (-1)^{s(i)}.
\]
According to the lemma, $|x+y|\leq 1$. By the inductive hypothesis, $x\geq 2$. Therefore
\[ f(n)\geq 2x-y-1 = 3x - (x+y) - 1\geq 6-1-1 > 2 \]
as desired.

\paragraph{Solution 3.}
For $r \in \{0, 1, 2\}$, define
\[ S_r(a,b) = \sum_{\substack{i\in [a,b) \\ i\equiv r \bmod 3}} (-1)^{s(i)}, \]
where $s(i)$ denotes the number of 1s in $i$'s binary representation.
The problem is equivalent to proving $S_0(0, 3n+1) > 1$ for all $n \geq 1$.

\begin{lemma*}
  For any integer $d$, $S_r(0, 2^d)$ is given by:
  \[
  \renewcommand{\arraystretch}{1.3}
  \begin{array}{c|ccc}
    d & S_0(0, 2^d) & S_1(0, 2^d) & S_2(0, 2^d) \\ \hline
    \text{d odd} & 3^{\frac{d-1}{2}} & -3^{\frac{d-1}{2}} & 0 \\
    \text{d even} & 2 \cdot 3^{\frac{d-2}{2}} & -3^{\frac{d-2}{2}} & -3^{\frac{d-2}{2}}
  \end{array}
  \]
\end{lemma*}

\begin{proof}
  Induction with $d \le 2$ being clear. For the inductive step, observe that
  \begin{align*}
    S_0(0, 2^d) &= S_0(0, 2^{d-1}) + S_0(2^{d-1}, 2^d) = S_0(0, 2^{d-1}) - S_{2^{d-1}}(0, 2^{d-1}) \\
    S_1(0, 2^d) &= S_1(0, 2^{d-1}) + S_1(2^{d-1}, 2^d) = S_1(0, 2^{d-1}) - S_{1+2^{d-1}}(0, 2^{d-1}) \\
    S_2(0, 2^d) &= S_2(0, 2^{d-1}) + S_2(2^{d-1}, 2^d) = S_2(0, 2^{d-1}) - S_{2+2^{d-1}}(0, 2^{d-1}).
  \end{align*}
  Using
  \[ 2^{d-1} \equiv \begin{cases}
    1 \bmod 3 & \text{$d$ odd} \\
    2 \bmod 3 & \text{$d$ even}
  \end{cases} \]
  and applying the inductive hypothesis gives the desired result.
\end{proof}

This proves the problem for powers of $2$.
To prove the problem for general $n$, split $[0, 3n+1)$ into blocks
\[
  [0, 3n+1) = [0, 2^{d_1}) \sqcup [2^{d_1}, 2^{d_1} + 2^{d_2})
    \sqcup [2^{d_1} + 2^{d_2}, 2^{d_1} + 2^{d_2} + 2^{d_3}), \dots\]
whose lengths are decreasing powers of $2$.
By the lemma,
\begin{align*}
  S_0(0, 2^{d_1})
  &\geq \begin{cases}
    3^{\frac{d_1-1}{2}} & \text{$d_1$ odd} \\
    2 \cdot 3^{\frac{d_1-2}{2}} & \text{$d_1$ even}
  \end{cases} \\
  S_0(2^{d_1}, 2^{d_1}+2^{d_2}) &= -S_{2^{d_1}}(0, 2^{d_2}) \geq 0
\end{align*}
and for all $i$,
\begin{align*}
  S_0(2^{d_1} + \dotsb + 2^{d_{i-1}}, 2^{d_1} + \dotsb + 2^{d_{i}})
  &= (-1)^{i-1}S_{2^{d_1} + \dotsb + 2^{d_{i-1}}}(0, 2^{d_i}) \\
  &\geq \begin{cases}
    -2 \cdot 3^{\frac{d_i-2}{2}} & \text{$d_i$ even} \\
    -1 \cdot 3^{\frac{d_i-1}{2}} & \text{$d_i$ odd}.
  \end{cases}
\end{align*}
Let $D= d_1$; assume $D \geq 4$ since checking $D \in \{1, 2, 3\}$ is easy.
Summing over all intervals gives
\[
  S_0(0, 3n+1) \geq 2 \cdot 3^{\frac{D-2}{2}} + 0 - \left(2 \cdot 3^{\frac{D-4}{2}}
  + 3^{\frac{D-4}{2}} + 2 \cdot 3^{\frac{D-6}{2}} + 3^{\frac{D-6}{2}} + \dotsb\right)
  = 3^{\frac{D-2}{2}} > 1
\]
when $D$ is even, and
\[
  S_0(0, 3n+1) \geq 3^{\frac{D-1}{2}} + 0 - \left(3^{\frac{D-3}{2}} + 2 \cdot 3^{\frac{D-5}{2}}
  + 3^{\frac{D-5}{2}} + 2 \cdot 3^{\frac{D-7}{2}} + \dotsb\right)
  = \tfrac{1}{2} \cdot 3^{\frac{D-3}{2}} > 1
\]
when $D$ is odd.

\begin{remark*}
  The following Python code calculates $\sum_{i=0}^{n}(-1)^{s(3i)}$ in $O(\log n)$ time
  using digit DP (and in $O(K \log n)$ time if $3$ is replaced by $K$):
\begin{lstlisting}[language=Python,numbers=none]
import functools

K = 3

def sgn(n: int) -> int:
    return -1 if bin(n).count('1') % 2 else 1

@functools.lru_cache(maxsize=None)
def f(n: int) -> list[int]:
    # Returns an array of size K where arr[i] = sum of sgn(j) over 0 <= j <= n with j % K = i
    ans = [0] * K
    if n == 0:
        ans[0] += 1
        return ans
    x = f(n // 2)
    for i in range(K):
        ans[2 * i % K] += x[i]
        ans[(2 * i + 1) % K] -= x[i]
    if n % 2 == 0:
        ans[(n + 1) % K] -= sgn(n + 1)
    return ans
\end{lstlisting}
\end{remark*}

\begin{remark*}
  Define
  \[f(n) = \sum_{i=0}^{\lfloor n/3\rfloor} (-1)^{s(3i)}.\]
  Then there exist constants $0 < c_1 < c_2$ such that
  \[
    \liminf_{n\to\infty} \frac{f(n)}{n^{\log_4(3)}} = c_1,
    \qquad \limsup_{n\to\infty}\frac{f(n)}{n^{\log_4(3)}} = c_2.
  \]
  The upper constant is $c_2 = \frac{2}{3}$, achieved when $n$ is a power of $4$.
\end{remark*}