Recurrence Relations for Sequence Counting Hamming Weights

Question

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero entries), $0$ and $1$ are abuses of notation to mean the vector all zeros and all ones, and $H \in \mathbb{F}^{n \times 2n}_2$ is defined as follows $$H = \left( \begin{array}{ccccccccc} 1 & 1 & 0 & 0 & 0 & 0 & \cdots & \cdots & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & \cdots & \cdots & 0\\ 1 & 0 & 1 & 0 & 1 & 1 & \cdots & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 0 & 1 & 0 & 1 & 0 & \cdots & 1 & 1\end{array} \right) $$
Then apparently one can use "simple induction" to prove $$a(n+1,k+2)=a(n,k+2)+b(n,k)$$ $$b(n+1,n+1)=a(n,k)+b(n,k)$$ Can anyone illuminate me on how this is done because I don't see it. This is not homework or anything (obviously school is out...), but just something I came across and is bothering me quite a bit. Thanks.

Answer 1

Let's set up some notation. Call that $n\times 2n$ matrix $H_n$. Let us call $C_n$ the subset (it is actually an $n$-dimensional subspace) of vectors $x\in\Bbb{F}_2^{2n}$ such that $H_n x^T=0$. We observe that the first column of $H_n$ is the all ones vector $1$ (continuing the abuse of notation - hopefully no confusion arises). This implies that $$ \tilde{C}_n=\{x\in\Bbb{F}_2^{2n}\mid H_nx^T=1\}=C_n+(100\ldots0), $$ the subset consisting of vectors not orthogonal to any row of $H_n$, is a coset of the subspace $C_n$. Or equivalently, a vector $x\in\tilde{C}_n$ if and only if it differs from a vector of $C_n$ in the first bit position.

We see that the matrix $H_{n+1}$ has the block structure $$ H_{n+1}=\left(\begin{array}{cc|ccc} 1&1&0&\cdots&0\\ \hline 1&0&*&*&*\\ \vdots&\vdots&*&*&*\\ 1&0&*&*&*\\ \end{array}\right), $$ where the $n\times2n$ block marked with $*$s is a copy of $H_n$. Let's write a vector $x\in\Bbb{F}_2^{2n+2}$ in the form $x=(x_1,x_2, \overline{x})$, where we single out the two first bits, and $\overline{x}\in\Bbb{F}_2^{2n}$ has the remaining $2n$ bits lumped together. We want to determine, when $x\in C_{n+1}$. For $x$ to be orthogonal to the first row of $H_{n+1}$ it is necessary and sufficient that $x_1=x_2$. If we have $x_1=x_2=0$, then $x$ is orthogonal to all the other rows of $H_{n+1}$, iff $\overline{x}\in C_n$, because $x_1=0$ and hence the two freshly added columns won't contribute to those inner products. On the other hand, if $x_1=x_2=1$, then $x_1=1$ contributes a $1$ to the inner products of $x$ and all the other rows of $H_{n+1}$, so $\overline{x}$ must also have inner product $1$ with all those rows to compensate. In other words we have just showed that $$ C_{n+1}=\{(0,0,\overline{x})\mid\overline{x}\in C_n\} \cup\{(1,1,\overline{x})\mid \overline{x}\in\tilde{C}_n\}. $$ Consequently we also get a recursive description $$ \tilde{C}_{n+1}=(100\ldots0)+C_{n+1}= \{(1,0,\overline{x})\mid\overline{x}\in C_n\} \cup\{(0,1,\overline{x})\mid \overline{x}\in\tilde{C}_n\}. $$

The recurrence formulas for the numbers of vectors of a given weight follow immediately from these description, because $w(0,0,\overline{x})=w(\overline{x})$, $w(1,1,\overline{x})=w(\overline{x})+2$ et cetera. In terms of the quantities $a(n,k)$ and $b(n,k)$ enumerating words of weight $k$ in $C_n$ and $\tilde{C}_n$ respectively the formulas read $$ \begin{aligned} a(n+1,k+2)&=a(n,k+2)+b(n,k),\\ b(n+1,k+1)&=a(n,k)+b(n,k). \end{aligned} $$