Finding recurrence relation 2 - Ternary sequences.

Question

for $n \ge 1$ , Let $f(n)$ be the number of ternary sequences {$0,1,2$} of length n,

that the sum of their characters are even, and they have at least one show of $0$.

How do i find the recurrence relation for f(n), thanks in advance.

Answer 1

HINT: First note that there are $3^n$ ternary sequences of length $n$, $2^n$ of which have no $0$, so there are $3^n-2^n$ that have at least one $0$. Let $g(n)$ be the number of these whose characters have odd sum, so that $f(n)+g(n)=3^n-2^n$. Let $\sigma$ be a ternary sequence of length $n$ that has at least one $0$ and whose characters have even sum.

• If $\sigma$ ends with $2$, then removing the last character of $\sigma$ leaves a ternary sequence of length $n-1$ with at least one $0$ whose characters have even sum. Conversely, every ternary sequence of length $n-1$ with at least one $0$ whose characters have even sum can be extended to exactly one ternary sequence of length $n$ that has at least one $0$, whose characters have even sum, and that ends in $2$. This accounts for $f(n-1)$ sequences; why?

• If $\sigma$ ends with $1$, then removing the last character of $\sigma$ leaves a ternary sequence of length $n-1$ with at least one $0$ whose characters have even sum. Conversely, every ternary sequence of length $n-1$ with at least one $0$ whose characters have odd sum can be extended to exactly one ternary sequence of length $n$ that has at least one $0$, whose characters have even sum, and that ends in $1$. How many sequences of length $n$ does this account for? You can express the answer in terms of the function $g$.

• If $\sigma$ ends with $0$, then removing the last character of $\sigma$ leaves a ternary sequence of length $n-1$ whose characters have odd sum, but it might not have a $0$. How many such sequences are there that do have at least one $0$? To finish, you need to work out how many do not have at least one $0$. That will be the number of sequences of length $n-1$ that do not contain a $0$ and whose characters have even sum, which simply means that they have an even number of $1$s.

Put the pieces together and express everything in terms of $f$.