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!
Best Answer
Hint: Hamming code is a perfect single error correcting code. This means that any vector of weight $i$ is either
Also the three options are mutually exclusive because the minimum Hamming distance between two codewords is three.