Return to Answer

Actually, these two conjectures are actually equivalent.

We need a lemma: Lucas' Theorem: $\binom{a}{b}$ is odd if and only if $a\&b=b$ where $\&$ is bitwise AND operation. Let $S_j$ be the set of integers $i$ such that $i\&j=i$. Thus, if the first relation

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ holds, we have $$a(n, -1) = \sum\limits_{j\in S_n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(j,0)$$ And therefore, $$\sum_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)=\sum_{j\in S_n}\sum_{k\in S_j}(-1)^{\text{wt}(j)-\text{wt}(k)}a(k,-1)$$ Swapping the sums, we have the right hand side equals to $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ All the other $k\in S_n$ vanishs the sum $\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$ because for every bit that is $1$ in $n$ and $0$ in $k$, it contribute a factor $1$ if that bit in $j$ is $0$ and $-1$ if that bit in $j$ is $1$. Therefore, the sum $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ is actually $a(n,-1)$, which implies the conjecture $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$. Similarly, we can derive the first conjecture using the second.

So, we only need to proof $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)$.

Notice that the sum $\sum_{j\in S_n}a(j,-1)$, if we take the combinatorial argument as granted, it counts the following permutations: for all the $k${th} bit of $n$ that is $0$, $\sigma(k)\le k$. This is because all the other bits when summed, cancelled out the restrictions. (If the $k$th bit of $n$ is $1$, that all the $S_k$ with $k$th bit $1$ with have $\sigma(k)> k$, and all the $S_k$ with $k$th bit $1$ with have $\sigma(k)>\le k$. So These two cancelled out if we sum the elements in $S_n$.) So we claim the number of such permutations is $a(n,0)$.

Actually, we can count the permutations as follows: for the $0$ bits of $n$ (call it $i_1,i_2,\dots,i_k$), we select the permutation one by one. We select $\sigma(i_l)$ to be one of $1,2,\dots,i_l$ except $\sigma(i_1),\dots,\sigma(i_{l-1})$. So this is $i_l-(\text{number of zeroes before $i_l$})$, that is, the number of ones before $i_l$. The rest of them we choose it freely, so it is $(\text{number of ones})!$. That is, we can assign $t$ to the $t$th one in the binary representation of $n$, or, the number of $1$ not after that bit, and take the product. Let $n=b_rb_{r-1}\dots b_0$ be its binary representation. So, the overall number of permutation is $\prod_{u=1}^r (\text{the number of ones not later than digit }b_u)$, and thus equals $a(n,0)$ (because the combinatorial meaning of $a(n,0)$ is such.)

Actually, these two conjectures are actually equivalent.

We need a lemma: Lucas' Theorem: $\binom{a}{b}$ is odd if and only if $a\&b=b$ where $\&$ is bitwise AND operation. Let $S_j$ be the set of integers $i$ such that $i\&j=i$. Thus, if the first relation

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ holds, we have $$a(n, -1) = \sum\limits_{j\in S_n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(j,0)$$ And therefore, $$\sum_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)=\sum_{j\in S_n}\sum_{k\in S_j}(-1)^{\text{wt}(j)-\text{wt}(k)}a(k,-1)$$ Swapping the sums, we have the right hand side equals to $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ All the other $k\in S_n$ vanishs the sum $\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$ because for every bit that is $1$ in $n$ and $0$ in $k$, it contribute a factor $1$ if that bit in $j$ is $0$ and $-1$ if that bit in $j$ is $1$. Therefore, the sum $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ is actually $a(n,-1)$, which implies the conjecture $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$. Similarly, we can derive the first conjecture using the second.

So, we only need to proof $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)$.

Notice that the sum $\sum_{j\in S_n}a(j,-1)$, if we take the combinatorial argument as granted, it counts the following permutations: for all the $k${th} bit of $n$ that is $0$, $\sigma(k)\le k$. This is because all the other bits when summed, cancelled out the restrictions. (If the $k$th bit of $n$ is $1$, that all the $S_k$ with $k$th bit $1$ with have $\sigma(k)> k$, and all the $S_k$ with $k$th bit $0$ with have $\sigma(k)\le k$. So These two cancelled out if we sum the elements in $S_n$.) So we claim the number of such permutations is $a(n,0)$.

Actually, we can count the permutations as follows: for the $0$ bits of $n$ (call it $i_1,i_2,\dots,i_k$), we select the permutation one by one. We select $\sigma(i_l)$ to be one of $1,2,\dots,i_l$ except $\sigma(i_1),\dots,\sigma(i_{l-1})$. So this is $i_l-(\text{number of zeroes before $i_l$})$, that is, the number of ones before $i_l$. The rest of them we choose it freely, so it is $(\text{number of ones})!$. That is, we can assign $t$ to the $t$th one in the binary representation of $n$, or, the number of $1$ not after that bit, and take the product. Let $n=b_rb_{r-1}\dots b_0$ be its binary representation. So, the overall number of permutation is $\prod_{u=1}^r (\text{the number of ones not later than digit }b_u)$, and thus equals $a(n,0)$ (because the combinatorial meaning of $a(n,0)$ is such.)

Actually, these two conjectures are actually equivalent.

We need a lemma: Lucas' Theorem: $\binom{a}{b}$ is odd if and only if $a\&b=b$ where $\&$ is bitwise AND operation. Let $S_j$ be the set of integers $i$ such that $i\&j=i$. Thus, if the first relation

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ holds, we have $$a(n, -1) = \sum\limits_{j\in S_n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(j,0)$$ And therefore, $$\sum_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)=\sum_{j\in S_n}\sum_{k\in S_j}(-1)^{\text{wt}(j)-\text{wt}(k)}a(k,-1)$$ Swapping the sums, we have the right hand side equals to $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ All the other $k\in S_n$ vanishs the sum $\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$ because for every bit that is $1$ in $n$ and $0$ in $k$, it contribute a factor $1$ if that bit in $j$ is $0$ and $-1$ if that bit in $j$ is $1$. Therefore, the sum $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ is actually $a(n,-1)$, which implies the conjecture $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$. Similarly, we can derive the first conjecture using the second.

So, we only need to proof $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)$.

(I have proved, but I need some time to write)

Actually, these two conjectures are actually equivalent.

We need a lemma: Lucas' Theorem: $\binom{a}{b}$ is odd if and only if $a\&b=b$ where $\&$ is bitwise AND operation. Let $S_j$ be the set of integers $i$ such that $i\&j=i$. Thus, if the first relation

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ holds, we have $$a(n, -1) = \sum\limits_{j\in S_n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(j,0)$$ And therefore, $$\sum_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)=\sum_{j\in S_n}\sum_{k\in S_j}(-1)^{\text{wt}(j)-\text{wt}(k)}a(k,-1)$$ Swapping the sums, we have the right hand side equals to $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ All the other $k\in S_n$ vanishs the sum $\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$ because for every bit that is $1$ in $n$ and $0$ in $k$, it contribute a factor $1$ if that bit in $j$ is $0$ and $-1$ if that bit in $j$ is $1$. Therefore, the sum $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ is actually $a(n,-1)$, which implies the conjecture $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$. Similarly, we can derive the first conjecture using the second.

So, we only need to proof $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)$.

Notice that the sum $\sum_{j\in S_n}a(j,-1)$, if we take the combinatorial argument as granted, it counts the following permutations: for all the $k${th} bit of $n$ that is $0$, $\sigma(k)\le k$. This is because all the other bits when summed, cancelled out the restrictions. (If the $k$th bit of $n$ is $1$, that all the $S_k$ with $k$th bit $1$ with have $\sigma(k)> k$, and all the $S_k$ with $k$th bit $1$ with have $\sigma(k)>\le k$. So These two cancelled out if we sum the elements in $S_n$.) So we claim the number of such permutations is $a(n,0)$.

Actually, we can count the permutations as follows: for the $0$ bits of $n$ (call it $i_1,i_2,\dots,i_k$), we select the permutation one by one. We select $\sigma(i_l)$ to be one of $1,2,\dots,i_l$ except $\sigma(i_1),\dots,\sigma(i_{l-1})$. So this is $i_l-(\text{number of zeroes before $i_l$})$, that is, the number of ones before $i_l$. The rest of them we choose it freely, so it is $(\text{number of ones})!$. That is, we can assign $t$ to the $t$th one in the binary representation of $n$, or, the number of $1$ not after that bit, and take the product. Let $n=b_rb_{r-1}\dots b_0$ be its binary representation. So, the overall number of permutation is $\prod_{u=1}^r (\text{the number of ones not later than digit }b_u)$, and thus equals $a(n,0)$ (because the combinatorial meaning of $a(n,0)$ is such.)

Although I am still working on a way to figure it out, I can claim that these two conjectures are actually equivalent.

We need a lemma: Lucas' Theorem: $\binom{a}{b}$ is odd if and only if $a\&b=b$ where $\&$ is bitwise AND operation. Let $S_j$ be the set of integers $i$ such that $i\&j=i$. Thus, if the first relation

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ holds, we have $$a(n, -1) = \sum\limits_{j\in S_n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(j,0)$$ And therefore, $$\sum_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)=\sum_{j\in S_n}\sum_{k\in S_j}(-1)^{\text{wt}(j)-\text{wt}(k)}a(k,-1)$$ Swapping the sums, we have the right hand side equals to $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ All the other $k\in S_n$ vanishs the sum $\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$ because for every bit that is $1$ in $n$ and $0$ in $k$, it contribute a factor $1$ if that bit in $j$ is $0$ and $-1$ if that bit in $j$ is $1$. Therefore, the sum $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ is actually $a(n,-1)$, which implies the conjecture $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$. Similarly, we can derive the first conjecture using the second.

Actually, these two conjectures are actually equivalent.

We need a lemma: Lucas' Theorem: $\binom{a}{b}$ is odd if and only if $a\&b=b$ where $\&$ is bitwise AND operation. Let $S_j$ be the set of integers $i$ such that $i\&j=i$. Thus, if the first relation

$$a(n, -1) = \sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}(\binom{n}{j}\operatorname{mod} 2)a(j,0)$$ holds, we have $$a(n, -1) = \sum\limits_{j\in S_n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}a(j,0)$$ And therefore, $$\sum_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)=\sum_{j\in S_n}\sum_{k\in S_j}(-1)^{\text{wt}(j)-\text{wt}(k)}a(k,-1)$$ Swapping the sums, we have the right hand side equals to $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ All the other $k\in S_n$ vanishs the sum $\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$ because for every bit that is $1$ in $n$ and $0$ in $k$, it contribute a factor $1$ if that bit in $j$ is $0$ and $-1$ if that bit in $j$ is $1$. Therefore, the sum $$\sum_{k\in S_n}a(k,-1)\sum_{j\text{ such that }k\in S_j,j\in S_n}(-1)^{\text{wt}(j)-\text{wt}(k)}$$ is actually $a(n,-1)$, which implies the conjecture $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)$. Similarly, we can derive the first conjecture using the second.

So, we only need to proof $a(n, 0) = \sum\limits_{j=0}^{n}(\binom{n}{j}\operatorname{mod} 2)a(j,-1)=\sum_{j\in S_n}a(j,-1)$.

(I have proved, but I need some time to write)