How do I show that there exists a code $C$ of length $n$ and distance at least $d$ such that $ max_{length(C) = n, d(C) \geq d} \mid C\mid \geq \frac{2^n}{\binom{n}{0} + \binom{n}{1} + ...+\binom{n}{d-1} } $?
My intuition is I have to use a corollary derived from the gilbert-varshamov bound theorem that says:
$\mid C\mid \geq \frac{2^{n-1}}{\binom{n-1}{0} + \binom{n-1}{1} + ...+\binom{n-1}{d-2} } $
and somehow exploit the fact that $\binom{y}{x} = \binom{y-1}{x-1} + \binom{y-1}{x}$ but I'm not sure if this is the best way to go about it.
We are working with binary vectors.
$\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{d-1}$ is the the number of vectors at Hamming distance strictly less than $d$ from the vector at the center. It is the volume of the Hamming sphere of radius $d-1$. Thus, $$D = |C|\left[\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{d-1}\right]$$ is the sum of the volumes of all the Hamming spheres of radius $d-1$ centered at the $|C|$ codewords. Note that $D$ is an overbound on the total number of vectors in these spheres because some of the spheres overlap each other since their surfaces are at distance $1$ from neighboring codewords at distance $d$, and so we are double-counting a lot. But, if $D < 2^n$, then there must exist vectors that are not in any of the spheres, and so are at distance $d$ or more from all the codewords in $C$. Find one such vector that is not in any of the Hamming spheres and include it in $C$ to create a new code $\hat{C}$. Note that $|\hat{C}| = |C|+1$. Now, calculate $$\hat{D} =|\hat{C}|\left[\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{d-1}\right]$$ and check whether $\hat{D} < 2^n$. If so, the same argument as above applies and we can add one more codeword to $\hat{C}$. Thus, augmentation of the code with one new codeword being added at each step can continue until we have a code $\tilde{C}$ for which $$\tilde{D} =|\tilde{C}|\left[\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{d-1}\right] \quad \mathbf {\geq} \quad 2^n.$$ At this point, the above argument cannot be used to say that we are guaranteed that there are more vectors available to be added to $\tilde{C}$; there probably are such vectors still available because $\tilde{D}$ grossly overestimates the total volume of the sphere, but this argument does not allow us to assert their existence. But, no matter, we have constructed a code $\tilde{C}$ for which $$|\tilde{C}| \geq \frac{2^n}{\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{d-1}}.$$ Note that this is a constructive argument in that there is a prescription for how to find $\tilde{C}$ but it is not a very useful prescription in that we have to search for a vector that is not in any of many Hamming spheres, and there is no help provided to make this search efficient.
But, but, but, you argue, we began with a code $C$ of minimum distance $d$. How can we be sure that such a code exists? That's easy: assuming that we are not doing something nonsensical like starting with $d > n$, the code $C = \{000\cdots 00, 111\cdots1000\cdots 00\}$ (where the second codeword has Hamming weight $d$) is a code of minimum distance $d$ that can serve as our starting point.