# Binary Hamming code - number of words weight $i$

Define $A_i$ as the number of words in binary Hamming code of weight $i$. Prove: $$A_1=0, A_0=1$$ $$(i+1)A_{i+1}+A_i+(n-i+1)A_{i-1}= {n \choose i}$$

I am a tad clueless as to how to proceed. I can show that for a given weight $i$, the number of columns of such weight of the parity-check matrix $H$ are precisely $n\choose i$. Every codeword $c$ of Ham must hold $c*H^t$. Furthermore, I can describe the generating matrix $G$ as being a matrix of the form [$A|I_{n-r}$], where there are $n\choose i$ rows in $A$ of weight $i$, for $2\le i \le n$.

I am certain the proof has to do with these two properties, yet I am unable to connect the points. Perhaps a proof with induction could be of use?

Any hints/direction towards the right way and what I should be looking at or focusing on will be extremely appreciated!

Hint: Hamming code is a perfect single error correcting code. This means that any vector of weight $i$ is either

• a codeword, or
• at a Hamming distance 1 from a uniquely determined codeword of weight $i-1$, or
• at a Hamming distance 1 from a uniquely determined codeword of weight $i+1$.

Also the three options are mutually exclusive because the minimum Hamming distance between two codewords is three.

Hint:

\begin{align} \binom{n}{i} &= \text{# of weight i words} \\ (i+1) A_{i+1} &= \text{# of weight i non-codewords distance 1 from a weight i+1 codeword} \\ A_i &= \text{# of weight i codewords} \\ (n-(i-1)) A_{i-1} &= \text{# of weight i non-codewords distance 1 from a weight i-1 codeword} \end{align}

As the Hamming code is a perfect $1$-error-correcting code, any non-codeword is distance $1$ from a unique codeword.

• Although I chose Jyrki's answer, this answer has been of great help to me too! Thanks! Commented Aug 25, 2014 at 17:43