Hadamard code, for fixed non-zero $x \in \{0,1\}^k$, how many $y \in \{0,1\}^k$ s.t $\langle x,y \rangle = 1$.
The exact details about the hadamard code can be found here: https://en.wikipedia.org/wiki/Hadamard_code
After some experimentation i thought that the amount of $y$'s that fit are $2^{k-1}$ and tried proving this with induction:
basis-step $k=1$:
$x = \{1\}\text{ gives me that }y = 1 = 2^{1-1}$
Induction step:
Let $x = (x_1 \dots x_k)$ and we have $2^{k-1}$ $y$'s that fit, then when we add a $k+1$-th element we get 2 situations:
1) $x_{k+1} = 0$
This suggests that $y_{k+1} \in \{0,1\}$, thus we get 2 extra choices thus the number of y's that fit are $2 \cdot 2^{k-1} = 2^k$
2) $x_{k+1} = 1$
Here we can either add a $0$ to the end of the $y$ string which gives us $2^{k-1}$ possible bitstrings, or we can add a $1$ and flip one $y_i = x_i = 1$ for some $1<i<k$ from a $1$ to a $0$.
The main problem that i encounter is proving that this process in the last part results in $2^{k-1}$ possibilities. Which $y_i$ do i flip? How do i know for sure that these flips don't create duplicates?
Any tips would be great!
Kees
Rather than "which $y_i$ do I flip", another way to think about the second case of the induction step might be as follows:
Suppose $x_{k+1} = 1$. We know from the induction hypothesis that there are $2^{k-1}$ $k$-tuples $(y_1, y_2, \dots, y_k) \in \{0,1\}^k$ such that $$x_1 y_1 + x_2 y_2 + \dots + x_k y_k \equiv 1 \pmod 2.$$ Call these the $k$-tuples of the first kind.
We also know that there are $2^k$ $k$-tuples in $\{0,1\}^k$ total, and therefore by complementary counting, there are $2^{k-1}$ $k$-tuples $(y_1, y_2, \dots, y_k) \in \{0,1\}^k$ such that $$x_1 y_1 + x_2 y_2 + \dots + x_k y_k \equiv 0 \pmod 2.$$ Call these the $k$-tuples of the second kind.
To obtain $2^k$ $(k+1)$-tuples in $\{0,1\}^{k+1}$, we can do the following:
We get $2^{k-1}$ distinct $y$'s from the first step, and $2^{k-1}$ distinct $y$'s from the second step. There is no overlap, because in the first step we only take $(y_1,\dots, y_k)$ of the first kind, and in the second step we only take $(y_1,\dots, y_k)$ of the second kind.
That being said, we could have accomplished this by flipping as well. Let $i$ be the very first position satisfying $x_{i} = 1$. For the second set of $2^{k-1}$ solutions, take any $k$-tuple of the first kind, flip $y_i$, and extend the result by $1$.
This does not create any duplicates, because we flip the same bit every time: if two $k$-tuples are equal after we flip the $i^{\text{th}}$ position in both, then they were equal before we did that.
In fact, flipping any bit where $x_i =1$ is a bijection between $k$-tuples of the first kind and $k$-tuples of the second kind, so that the two methods are equivalent. (Noticing and proving this can lead you to a non-inductive solution: since there is a bijection between the two kinds, there must be an equal number $2^{k-1}$ of each kind.)
There is also a third case you haven't considered. What if $x = (0,0,\dots,0,1)$? Then the inductive hypothesis does not apply to $(x_1, x_2, \dots, x_k)$, because $(x_1, x_2, \dots, x_k)$ is the zero vector.
Of course, it's very easy to figure out what set of $2^k$ $y$'s have $\langle x,y\rangle = 1$ in this case: it's simply all vectors $y$ with $y_{k+1} = 1$.