Proof by mathematical induction of a recursion equation

The recursion equation for the problem:

A "codeword" from alphabet {0,1,2,3} is said to be "legitimate" if it contains an even number of zeros. Thus for instance, the codeword 31010 is legitimate whereas 01010 is not. How many n-letter codewords are legitimate ?

is N(n) = 2^(2n-1) + 2^(n-1)

Can some one help me with proving N(n) by mathematical induction ?

I know that the first step is to show that N(1) is true.
So if I plug in n=1 in the equation above the answer is three and it is true becasue legitimate codewords that are 1-letter long are {1},{2} and {3} and therefore there are three.

I think the next step is to assume that N(n) is true and then to see whether or not N(n+1) is true by plugging in n+1 for n in the recursion equation above.


Thanks in advance (Itwasntme)

You can't just put n+1 to it, you have to prove it :) It means count all such words for n+1.

1. Prove for N(0):

There are only 3 "legitimate" values and N(0) = 3. So it's true!

2. Prove for N(n+1) if we know that it's true for N(n)

Let's count how many "legitimate" words could be for N(n+1):
a) We can construct "legitimate" word length n+1 by adding 1, 2 or 3 to "legitimate" word of length n, so there will be 3*N(n) such "legitimate" words;
b) By adding 0 to a non "legitimate" word of length n. There will be (2^2n-N(n)) such "legitimate" words of length n;



So it's totally true ;)

Hello ialbrekht

Quote:

---

Originally Posted by ialbrekht

You can't just put n+1 to it, you have to prove it :) It means count all such words for n+1.

1. Prove for N(0):

There are only 3 "legitimate" values and N(0) = 3. So it's true!

2. Prove for N(n+1) if we know that it's true for N(n)

Let's count how many "legitimate" words could be for N(n+1):
a) We can construct "legitimate" word length n+1 by adding 1, 2 or 3 to "legitimate" word of length n, so there will be 3*N(n) such "legitimate" words;
b) By adding 0 to a non "legitimate" word of length n. There will be (2^2n-N(n)) such "legitimate" words of length n;



So it's totally true ;)

---

I like the simplicity of your argument, but I don't quite understand it. Can you clear up some questions for me?

• In (a) when we construct a legitimate word of length n+1 from a word of length n, where does the extra 1, 2 or 3 get added?

• In (b), where does the extra zero get added to the non-legitimate word?

• How can you be sure that none of the new words formed by method (a) aren't the same as some of the words formed by method (b)?

Grandad

PS Ah - I have it. It really is simple, isn't it? Every legitimate word of length n+1 either ends in (i) a zero or (ii) a non-zero. If we remove the last digit, then, we get a word of length n which is either (i) non-legitmate, or (ii) legitimate, respectively.