Consider the set of words of length n over the 3-letter alphabet {0，1，2} a) Prove that...

Consider the set of words of length n over the 3-letter alphabet {0，1，2}

a) Prove that the number of such words with an even number of 0’s is (3^n+1)/2 and the number of such words with an odd number of 0’s is (3^n-1)/2. (Hint: Try a proof by induction.)

b) Prove that C(n,0)*2^n+C(n,1)2^(n-2)+C(n,4)2^(n-4)+....+C(n,q)2^(n-q)=(3^n+1)/2.