Note: We are talking about binary codes.
Definition 1: For integers $1 ≤ d ≤ n$, a code $C$ is an $(n, d)$-code if it has length $n$ and minimum distance $d_H (C) ≥ d$. An $(n, M, d)$-code is an $(n,d)$-code of size $M$.
Definition 2: For integers $1 ≤ d ≤ n$, let $A(n,d)$ be the largest $M$ such that there exists an $(n, M, d)$-code. An $(n, d)$-code is optimal if has size $A(n, d)$.
Prove that for any integer $n ≥ 2$ and $1 ≤ d ≤ n$, we have $$A(n, d) ≤ 2A(n − 1, d)$$.
What I did: It suffices to prove that given $C$, a $(n,d)$-code, we can find $C'$, a $(n-1,d)$-code, such that $|C| \leq 2|C'|.$
Next what I think is that we have to truncate $C$ by deleting the last bit of every codeword. This will make $C'$ a code of length $n-1$ but doing so will affect the minimum distance as we might delete the bits where the two codes are distinct. Any Idea how to proceed?
Proof
Let $C$ be an $(n,d)$-code.
Let $n(0)$ and $n(1)$ denote the number of codewords in $C$ ending with $0$ and $1$, respectively.
We claim that either $n(0)$ or $n(1)$ $\geq |C|/2.$
Proof of claim:
If either $n(0)$ or $n(1) = |C|/2$, we are done.
Assume $ n(1) < |C|/2$. We need to show $n(0)> |C|/2.$ $$|C|=n(0)+n(1)< n(0)+|C|/2.$$ So, $$n(0)> |C|/2.$$ This proves the claim.
Now, WOLG, assume $n(0) \geq |C|/2.$
Consider $C^* \subset C $ containing only codes ending with $0$, i.e, we have $|C^*|=n(0).$
Define $C'$ to be a code obtained by deleting the last bit of codewords in $C^*$.
Note that $d_H(C')=d_H(C) \geq d$, $C'$ is a code of lenght $n-1$, and $|C'|=|C^*|$.
Moreover, from the claim, $$|C'|=|C^*|=n(0) \geq |C|/2.$$
This proves that given any $C$, a $(n,d)$-code, we can find $C'$, a $(n-1,d)$-code such that $$|C| \leq 2|C'|.$$
Hence, for $n \geq 2$, and $1\leq d \leq n$, $$A(n,d)≤2A(n−1,d).$$