Closed form for $\sum\limits_{k=0}^{n} [\operatorname{wt}(k) = m]$ where $\operatorname{wt}(n)$ is the binary weight of $n$

Question

• Let $\operatorname{wt}(n)$ be A000120 (i.e., number of $1$'s in binary expansion of $n$).
• Let $a(n,m)$ be the family of integer sequences such that $$ a(n,m) = \sum\limits_{k=0}^{n} [\operatorname{wt}(k) = m]. $$
• Let $T(n,k)$ be A272020 (i.e., irregular triangle read by rows: strictly decreasing sequences of positive numbers given in lexicographic order). Here row $n$ given by the exponents in the binary expansion of $2n$. We also consider that numeration of columns starts with $1$.
• Let $b(n,m)$ be the family of integer sequences such that $$ b(n,m) = \sum\limits_{k=0}^{\min(m,\operatorname{wt}(n+1)-1)} \binom{T(n+1,k+1)-1}{m-k}. $$

I conjecture that $$ b(n,m) = a(n,m). $$

Here is the PARI/GP program to check it numerically:

a(n,m) = sum(k=1, n, hammingweight(k) == m)
b(n,m) = my(v1); v1 = Vecrev(binary(n+1)); v1 = Vecrev(select(x->(x>0),v1,1)); sum(k=0, min(m,#v1-1), binomial(v1[k+1]-1,m-k))
test1(n,m) = b(n,m) == a(n,m)

Is there a way to prove it?

Answer 1

For $n > 0$ let $\ell(n) = \lfloor \log_2(n) \rfloor$ so that $n = 2^{\ell(n)} + r_n$ where $0 \le r_n < 2^{\ell(n)}$. Note that $\ell(n) = T(n, 1) - 1$.

Then by partitioning the numbers $k$ up to $n$ according to whether $\ell(k) = \ell(n)$ we have $$a(n, m) = \begin{cases} 1 & \textrm{if } m = 0 \wedge n \ge 0 \\ 0 & \textrm{otherwise if } m \le 0 \vee n \le 0 \\ a(n - 2^{\ell(n)}, m-1) + \binom{\ell(n)}{m} & \textrm{otherwise} \end{cases}$$

If we unroll the recurrence for $s$ steps we get $$a(n, m) = a\left(n - \sum_{i=1}^{s+1} 2^{T(n,i)-1}, m-s-1\right) + \sum_{k=0}^s \binom{T(n,s+1) - 1}{m-s}$$

If we set $s = \min(m, \operatorname{wt}(n)-1)$ then $$a(n, m) = a\left(n - \sum_{i=1}^{s+1} 2^{T(n,i)-1}, m-s-1\right) + b(n-1, m)$$

Now consider three cases:

1. $m < \operatorname{wt}(n)$.
   Setting $s=m$ we get $a(n, m) = a\left(n - \sum_{i=1}^{m+1} 2^{T(n,i)-1}, -1\right) + b(n-1, m) = b(n-1, m)$

2. $m = \operatorname{wt}(n)$
   Setting $s=m-1$ we get $a(n, m) = a(0, 0) + b(n-1, m) = 1 + b(n-1, m)$

3. $m > \operatorname{wt}(n)$
   Setting $s = \operatorname{wt}(n) - 1$ we get $a(n, m) = a(0, m-\operatorname{wt}(n)) + b(n-1, m) = b(n-1, m)$

Combining the cases we have $$a(n, m) = [m = \operatorname{wt}(n)] + b(n-1, m)$$ But it's clear that $$a(n, m) = [m = \operatorname{wt}(n)] + a(n-1, m)$$ so $a(n-1, m) = b(n-1, m)$ is an identity.