Can someone help me derive a recurrence relation to find the number of n-digit ternary sequences with an even number of 0's and 1's?
I know that you need to break it down into cases where the sequence starts with either a 0 OR a 1 or a 2 and based on that you determine the expression for a sequence of length n based on the subsequences of length n-1. However, I'm stuck in breaking it down into the cases and going forward from there.
Thanks for any help in advance!
Here is an answer using generating functions. With the digits $0,1$ and $2$ represented by $u,v$ and $w$ your sequences have the generating function $$(u+v+w)^n.$$
Therefore sequences with even count of zero digits have the generating function $$\frac{1}{2} \left((u+v+w)^n + (-u+v+w)^n\right).$$ We also have an even number of one digits, which gives $$\frac{1}{4} \left((u+v+w)^n + (-u+v+w)^n\right) + \frac{1}{4} \left((u-v+w)^n + (-u-v+w)^n\right).$$ We are only interested in the count so we put $u=v=w=1$ to obtain $$\frac{1}{4} 3^n + \frac{1}{2} + \frac{1}{4} (-1)^n.$$ This is the following sequence: $$1, 1, 3, 7, 21, 61, 183, 547, 1641, 4921, 14763,\ldots$$ which is OEIS A122983.