Show that for any n ≥ 1, there is an error-detecting set of strings of length n, using the digits 0, 1, and 2, that has 3n−1 strings?

Question

Can anyone please show me a proof by induction for this?

A set of error-detecting strings is a set of strings that differ by more than one character.

For example: for {0,1,2} for n = 2: {00,11,22}

Show that for any n ≥ 1, there is an error-detecting set of strings of length n, using the digits 0, 1, and 2, that has 3^(n−1) strings?

And afterwards a proof for this:

Show that if we use k symbols, for any k ≥ 2, then there is an errordetecting set of strings of length n, using k different symbols as “digits,” with kn−1 strings, but no such set of strings with more than k^(n−1) strings.

Answer 1

If you don't need an induction argument, just take all length $n$ strings for which the sum of the digits is $0 \pmod 3$. Any two strings which differ in only one of the first $n-1$ bits will also differ in the last. You can't have two strings which agree on the first $n-1$ bits because they would have the same last bit. The same argument works for any number of different digits.