TITLE: Recurrence Relations for Sequence Counting Hamming Weights
QUESTION [1 upvotes]: 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.

REPLY [0 votes]: 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}
$$
{"set_name": "stack_exchange", "score": 1, "question_id": 1372090}