I'm trying to prove that for $2^n$ binary strings of length $n$ ($n$ being positive integer), there exists a subset of $2^{n-1}$ binary strings where no two strings differ in only $1$ number (e.g. $01$ and $11$ differ in only $1$ number i.e. change $0$ to $1$ and it is the same).
Base case would be $n=1$ ($2^1=2, 2^{1-1}=1$). ${1, 0}$ are two strings and both differ from each other by only $1$ number so only $1$ can be in the subset.
Induction Hypothesis would be assume that for every $2^n$ strings, $2^{n-1}$ subset exists where no strings differ in only $1$ integer. Prove for $n+1.$
Proof I tried (just started learning proofs) was, let $n+1 = m.$ Then with $2^m$ strings, $2^{m-1}$ subset strings exist where no two strings differ by only $1$ number, which is assumed in the induction hypothesis. I'm guessing I'm using this wrong, because well.. it seemed too obvious. Is there any way for me to realize, when doing proofs, that the induction hypothesis is being used incorrectly?
There is one proof that does not require induction. Just let the subset be the set of "odd" strings, where we call a string odd if the sum of its bits is odd.
It is easy to see that the subset contains exactly $2^{n-1}$ strings. On the other hand, any two odd strings must differ by more than one places, as otherwise one of them is "even".