5
$\begingroup$

Let

  • $T(n,k)$ be A131823, i.e., integer coefficients whose ordinary generating function for the $n$-th row is $ \displaystyle{ \prod_{i=0}^{n-1} (1 + x^{2^i})^{n-i} }$.
  • $\operatorname{wt}(n)$ be A000120, i.e., number of ones in the binary expansion of $n$. Here $$ \operatorname{wt}(2n+1) = \operatorname{wt}(n) + 1, \\ \operatorname{wt}(2n) = \operatorname{wt}(n), \\ \operatorname{wt}(0) = 0. $$

I conjecture that for $ 0\leqslant k \leqslant 2^{n+1} - (n+1) $ we have $$ \sum\limits_{j=0}^{k} \binom{n+j}{j} (-1)^{\operatorname{wt}(k-j)} = T(n,k). $$

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

T1(n,k)=local(A=[1]); if(n==0, 1, for(i=0, n-1, A=concat(Vec((Polrev(A)+O(x^(#A+i)))/(1-x)), Vec(O(x^(#A))+Pol(Vec(Ser(A)/(1-x)))))); A[k+1]) T2(n,k) = my(A = 1); (-1)^wt(k) + sum(j=1, k, (A*=((n+j)/j))*(-1)^wt(k-j)) test(n) = vector(2^(n+1)-(n+1), i, T2(n,i-1)) == vector(2^(n+1)-(n+1), i, T1(n,i-1))

Is there a way to prove it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Yes, there is a way. By the way, this holds not only for $0\leqslant k\leqslant 2^{n+1}-n-1$ (note that the largest $k$ for which $T(n,k)>0$ is $k=2^{n+1}-n-2$), but also for all $k$ up to $2^{n+1}-1$.

We use the standard telescoping identity $$F_m(x):=(1+x)(1+x^2)\ldots (1+x^{2^m})=\frac{1-x^{2^{m+1}}}{1-x}$$ (which is proved by multiplying by $1-x$ and consecutively using the identity $(1-t)(1+t)=1-t^2$ in the left hand side expression $m+1$ times). It follows that $$G(x):=\prod_{i=0}^{n-1}(1+x^{2^i})^{n-i}=\prod_{i=0}^{n-1}F_i(x)=(1-x)^{-n-1}(1-x)(1-x^2)\ldots(1-x^{2^n})\\ =\sum_{j=0}^\infty(-1)^j{-n-1\choose j}x^j\cdot \sum_{s=0}^{2^{n+1}-1}(-1)^{ \operatorname{wt}(s)}x^s=\sum_{j=0}^\infty{n+j\choose j}x^j\cdot \sum_{s=0}^{2^{n+1}-1}(-1)^{ \operatorname{wt}(s)}x^s,$$ and taking the coefficient of $x^k$ in $G(x)$ (which is $T(n,k)$) we get your identity.

Improve this answer
$\endgroup$

You must log in to answer this question.