Sum of rows of Pascal's triangle modulo 8

 Pascal's triangle modulo $m$ can present interesting numerical structures. For instance, for $m=2$, the resulting triangle is the fractal Sierpinski's triangle. We consider the sum of the $n$-th row of Pascal's triangule mod 8. 

This sum (OEIS A385285) is defined as $a(n) = \sum_{k=0}^n \left[\left(\begin{array}{c}n\\k\end{array}\right) \mod 8\right]$

In particular, we construct a formula for this sum using the results in Ref. [1]. We follow the notation in Ref. [1]. Let $N_n(t,m)$ be defined as the numbers of integers in the $n$-th row of Pascal's triangle that is congruent to $t$ modulo $m$.

Then $a(n) = \sum_{k=1}^7 kN_n(k,8)$. We split this sum into three parts: $x_1 = 4N_n(4,8)$, 

$x_2 = 2N_n(2,8)+6N_n(6,8)$ and $x_3 =  N_n(1,8)+3N_n(3,8)+5N_n(5,8)+7N_n(7,8)$.

Defne $v_i$ and $s_i$ as the length of the $i$-th block of $0$'s (resp. $1$'s) in the binary representation of $n$. For a binary string $s$, let $n_s$ denote the number of occurrences of $s$ in the binary representation of $n$. In particular, $n_1$ is the Hamming weight of $n$ (OEIS A000120). Let $r=2^{n_1}$. This is also known as Gould's sequence or Dress's sequence (OEIS A001316). We will show that $a(n)$ is divisible by $r$.

The following results were shown in Ref. [1]:

$x_1 = 4N_n(4,8) = r(4n_{001}+n_{011}+n_{01}(n_{01}-1)/2)$.

$2N_n(2,8) = \left\{\begin{array}{ll}r(n_{01}-n_{001}) & \mbox{if } n_{11}=0\\r((n_{01}-n_{011})/2+n_{0011}) & \mbox{if } n_{11}=1\\r(n_{01}/2) & \mbox{if } n_{11}\geq 2\end{array}\right.$

$6N_n(6,8) = \left\{\begin{array}{ll}3r(n_{001}) & \mbox{if } n_{11}=0\\3r((n_{01}+n_{011})/2-n_{0011}) & \mbox{if } n_{11}=1\\3r(n_{01}/2) & \mbox{if } n_{11}\geq 2\end{array}\right.$

This implies that

$x_2 = \left\{\begin{array}{ll}r(n_{01}+2n_{001}) & \mbox{if } n_{11}=0\\r(2n_{01}+n_{011}-2n_{0011}) & \mbox{if } n_{11}=1\\r(2n_{01}) & \mbox{if } n_{11}\geq 2\end{array}\right.$

For the cases $N_n(i,8)$ where $i$ is odd, [1, Theorem C] splits them into 13 cases. Combining the results of these 13 cases to derive $x_3$, we get the following table:

Case No.    $x_3$

(i)                $4r$

(ii)                $r$

(iii)                $3r$

(iv)                $4r$

(v)                $4r$

(vi)                $4r$

(vii)                $4r$

(viii)                $2r$

(ix)                $4r$

(x)                $4r$

(xi)                $2r$

(xii)                $4r$

(xiii)                $2r$

Note that in most of the cases, $x_3$ is equal to $4r$. Using this information for $x_i$, we can compute $a(n) = x_1+x_2+x_3$. Note that each $x_i$ is divisible by $r$ and this shows that $a(n)$ is also divisible by $r$.

Determining the case number require computation of $v_i$, $s_i$ and $n_s$ for various strings $s$. Noting that $x_3$ are the same for various cases, these cases can be combined. In particular,

$x_3 = \left\{\begin{array}{ll}r & \mbox{if case (ii)}\\ 3r & \mbox{if case (iii)}\\2r & \mbox{if case (viii) or (xi) or (xiii)}\\4r & \mbox{otherwise}\end{array}\right.$

Python code to compute $a(n)$ using this method can be found in OEIS A385285 (and the related sequence OEIS A385394).       

[1] James G. Huard, Blair K. Spearman, and Kenneth S. Williams, Pascal's triangle (mod 8), European Journal of Combinatorics, vol. 19, no. 1 (1998), pp. 45-62.