Proof by mathematical induction of a recursion equation

• Sep 28th 2009, 05:56 PM
thw002
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.

• Sep 29th 2009, 07:42 AM
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;

\$\displaystyle N(n+1) = 3N(n)+(2^{2n}-N(n)) = 2^{2(n+1)-1}+2^{(n+1)-1}\$

So it's totally true ;)
• Sep 29th 2009, 12:44 PM
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;

\$\displaystyle N(n+1) = 3N(n)+(2^{2n}-N(n)) = 2^{2(n+1)-1}+2^{(n+1)-1}\$

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)?