# Sequences that sum up to Dowling numbers

Let $$a(n,k)$$ be the sequence of $$k$$-Dowling numbers (for more information see A007405 and its CROSSREFS section) with e.g.f. $$\operatorname{exp}\left(x + \frac{\operatorname{exp}(kx) - 1}{k}\right)$$ Let $$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$ $$f(n)=n-2^{\ell(n)}$$ $$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2$$ Here $$f(n)$$ is the same as $$n$$ without the most significant bit and $$T(n,k)$$ is the $$(k+1)$$-th bit from the right side in the binary representation of $$n$$.

Let $$b(n,m,k)$$ be an integer sequence such that $$b(n,m,k)=mb(f(n),m,k)+\sum\limits_{j=0}^{\ell(n)} k(1-T(n,j))b(f(n)+2^j(1-T(n,j)),m,k)$$ Here $$b(n,1,1)$$ is A341392.

Let $$s(n,m,k)$$ be an integer sequence such that $$s(n,m,k)=\sum\limits_{j=0}^{2^n-1}b(j,m,k)$$ I conjecture that $$s(n,1,k)=a(n,k)$$ I also conjecture that e.g.f. for $$s(n,m,k)$$ is $$\operatorname{exp}(x + m\frac{\operatorname{exp}(kx) - 1}{k})$$ Here is the PARI prog to verify these conjectures:

s(n, m, k)=my(v, v1); v=vector(2^n, i, 0); v[1]=1; for(i=1, #v-1, my(L=logint(i, 2), A=i-2^L); v[i+1]=m*v[A+1] + sum(j=0, L, my(B=bittest(i, j)); k*(1-B)*v[A + 2^j*(1-B) + 1])); v1=[1]; for(i=1, n, v1=concat(v1, sum(j=0, 2^i-1, v[j+1]))); v1
[n, m, k]=[10, 1, 2]
x=s(n, m, k)
z='z+O('z^(n+1)); x1=Vec(serlaplace(exp(z + m*(exp(k*z) - 1)/k)))
test=x==x1


Is there a way to prove it?

Cleaning up the notation a bit,

$$b_{m,k}(n) = m\, b_{m,k}(n-2^{\ell(n)}) + k \sum_{j=0}^{\ell(n)-1} [n \,\&\, 2^j = 0] \,b_{m,k}(n - 2^{\ell(n)} + 2^j)$$ where $$\&$$ is bitwise AND. $$s_{m,k}(n) = \sum_{j=0}^{2^n-1} b_{m,k}(j)$$

Let $$\operatorname{wt}(n)$$ be the Hamming weight of $$n$$, and for an arbitrary polynomial $$p(z)$$ define $$s_{m,k}^p(n) = \sum_{j=0}^{2^n-1} p(\operatorname{wt}(j)) b_{m,k}(j)$$ This generalises $$s_{m,k} = s_{m,k}^{z^0}$$. The differences reduce nicely:

$$\begin{eqnarray*}s_{m,k}^p(n) - s_{m,k}^p(n-1) &=& \sum_{j=2^{n-1}}^{2^n-1} p(\operatorname{wt}(j)) b_{m,k}(j) \\ %&=& \sum_{j=0}^{2^{n-1}-1} p(\operatorname{wt}(2^{n-1} + j)) b_{m,k}(2^{n-1} + j) \\ &=& \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) b_{m,k}(2^{n-1} + j) \\ %&=& \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) \left( m\, b_{m,k}(j) + k \sum_{i=0}^{n-2} [j \,\&\, 2^i = 0] \,b_{m,k}(j + 2^i) \right) \\ &=& m \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) b_{m,k}(j) + k \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) \sum_{i=0}^{n-2} [j \,\&\, 2^i = 0] \,b_{m,k}(j + 2^i) \\ %&=& m s_{m,k}^{E_z p}(n-1) + k \sum_{j=0}^{2^{n-1}-1} \sum_{i=0}^{n-2} [j \,\&\, 2^i = 0] p(\operatorname{wt}(j + 2^i)) b_{m,k}(j + 2^i) \\ %&=& m s_{m,k}^{E_z p}(n-1) + k \sum_{j=0}^{2^{n-1}-1} \operatorname{wt}(j) p(\operatorname{wt}(j)) b_{m,k}(j) \\ &=& m s_{m,k}^{E_z p}(n-1) + k s_{m,k}^{zp}(n-1) \\ \end{eqnarray*}$$ where $$E_z$$ is the raising operator $$(E_z p)(z) = p(z+1)$$.

With the base case $$s_{m,k}^p(0) = p(0)$$, we get $$s_{m,k}(n) = (1 + mE_z + kz)^n z^0 \mid_{z=0}$$.

Two useful subresults towards the main proof:

Theorem: $$(mE_z + kz)^d z^0 \mid_{z=0} = \sum_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i$$ where $$\genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i}$$ is a Stirling number of the second kind.

By induction.

• In the base case, $$d=0$$, we have $$1 = \genfrac{\lbrace}{\rbrace}{0pt}{}{0}{0}$$.
• Note that by repeated application of $$E_z z = (z+1)E_z$$ we can rewrite $$(mE_z + kz)^d$$ as $$\sum_{i=0}^d k^{d-i} m^i q_{k,m}(z) E_z^m$$ where the $$q_{k,m}$$ are polynomials. Then $$(mE_z + kz)^d z^0 \mid_{z=0} = \sum_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i$$ is equivalent to $$\forall i \in [0,d]: q_{d-i,i}(0) = \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i}$$. Now we multiply on the right to get $$\begin{eqnarray*}(mE_z + kz)^{d+1} &=& \sum_{i=0}^d k^{d-i} m^i q_{k,m}(z) E_z^m (mE_z + kz) \\ &=& \sum_{i=0}^d k^{d-i} m^{i+1} q_{k,m}(z) E_z^{m+1} + k^{d-i+1} m^i q_{k,m}(z)(z+m) E_z^m \\ \end{eqnarray*}$$ so $$q_{k,m}(0) = q_{k,m-1}(0) + k q_{k-1,m}(0)$$ $$= \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m-1}{m-1} + k \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m-1}{m}$$ $$= \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m}{m}$$.

Theorem: $$(\exp(z)-1)^i = \sum_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n$$

Surely standard. By induction: $$(\exp(z)-1)^0 = 1 = \sum_{n \ge 0} \frac{0!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{0} z^n$$ checks out, and $$\begin{eqnarray*}\left(\sum_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n\right)(\exp(z)-1) &=& \left(\sum_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n\right)\left( \sum_{j \ge 1} \frac{1}{j!} z^j\right) \\ &=& \sum_{n \ge i+1} z^n \sum_{j=1}^n \frac{i!}{(n-j)!j!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n-j}{i} \\ &=& \sum_{n \ge i+1} \frac{i!}{n!} z^n \sum_{j=1}^n \binom{n}{j} \genfrac{\lbrace}{\rbrace}{0pt}{}{n-j}{i} \\ \end{eqnarray*}$$

The inner sum counts pointed partitions of $$n$$ items into $$i+1$$ sets, so equals $$(i+1) \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i+1}$$, completing the proof.

Theorem: $$\sum_{n \ge 0} \frac{s_{m,k}(n)x^n}{n!} = \exp\left(x + m\frac{\exp(kx) - 1}{k}\right)$$

For the LHS we have $$\begin{eqnarray*}\sum_{n \ge 0} \frac{s_{m,k}(n)x^n}{n!} &=& \sum_{n \ge 0} \frac{x^n}{n!} \sum_{d=0}^n \binom{n}{d} \sum_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i \\ &=& \sum_{n,i,j \ge 0} \frac{1}{n!} \binom{n}{i+j} \genfrac{\lbrace}{\rbrace}{0pt}{}{i+j}{i} x^n m^i k^j \end{eqnarray*}$$

For the RHS we have $$\begin{eqnarray*}\exp\left(x + m\frac{\exp(kx) - 1}{k}\right) &=& \exp\left(x + mx\frac{\exp(kx) - 1}{kx}\right) \\ &=& \sum_{u \ge 0} \frac{x^u}{u!} \left(1 + m\frac{\exp(kx) - 1}{kx}\right)^u \\ &=& \sum_{u,i \ge 0} \frac{x^u}{u!} \binom{u}{i} \left(\frac{m}{kx} \right)^i (\exp(kx) - 1)^i \\ &=& \sum_{u,i \ge 0} \frac{x^u}{u!} \binom{u}{i} \left(\frac{m}{kx} \right)^i \sum_{v \ge i} \frac{i!}{v!} \genfrac{\lbrace}{\rbrace}{0pt}{}{v}{i} (kx)^v \\ &=& \sum_{n,i,j \ge 0} \frac{1}{n!} \binom{n}{i+j} \genfrac{\lbrace}{\rbrace}{0pt}{}{i+j}{i} x^n m^i k^j \end{eqnarray*}$$ where the final line uses the substitutions $$j = v-i$$ and $$n = u+j$$.

Finally, note that the operator expression for $$s_{m,k}$$ gives the elegant formulation of the main theorem as $$\exp(x(1 + mE_z + kz)) z^0 \mid_{z=0} = \exp\left(x + m\frac{\exp(kx) - 1}{k}\right)$$