Representation of a 2-power as sum of \(k\) 2-powers: a recursive formula (Q1938563)

Let \(U(\ell,k)\) denote the number of distinct compositions of \(\ell\) as a sum of \(k\) powers of two (where order matters). Thus, for example, \(U(10,3) = 6\), arising from the representations \(10 = 8+1+1\) and \(10 = 4+4+2\) and their permutations. The behavior of \(U(\ell,k)\) is quite erratic; it can be regularized by defining \(W(\sigma, k) = \max_{\ell:s_2(\ell) = \sigma} \{ U(\ell,k) \}\), where \(s_2(\ell)\) is the number of \(1\) bits in the binary representation of \(\ell\). In a previous paper [J. Number Theory 130, No. 9, 2011--2027 (2010; Zbl 1198.11074)], the second author proved that \[ W(\sigma,k) = k! \sum_{1 \leq n < k} {{W(1,n)}\over {n!}} \cdot {{W(\sigma-1,k-n)} \over {(k-n)!}}, \] thus reducing the computation of \(W\) to \(W(1,n)\). In this paper the authors give a recursive formula, involving binomial coefficients, for \(W(1,n)\). From this they derive the congruence \(W(1,n) \equiv 4 + (-1)^n \pmod 8\) for \(n \geq 3\). They also state some conjectures for congruence modulo higher powers of \(2\).