I'm trying to find a recursive formula for all the ternary (using ${0,1,2}$) sequences of length $n$ which contain at least one zero, and have an even sum of digits.
My attempt so far is added below. I think the idea is right, but the recurrence relation I get fails when setting in numbers (and it's not always an integer..). any ideas?
Denote with $f\left(n\right)$ the number of legal sequences as in the question, $\bar{f}\left(n\right)$ as the number of sequences with at least one 0 with an odd number of digits, and as $g\left(n\right)$ the number of sequences with an even sum of digits and with no zeroes.
For any sequence, the sum of digits would be even if and only if there is an even number of 1s, therefore any legal sequence of length $n$ can be achieved in a unique way out of the following:
• Starting from a sequence where the digits are even and there is no zero, append zero at the end. There are $g\left(n-1\right)$ such sequences.
• Starting from a legal sequence of length $n-1$, append 0 or 2 at the end, adding $2f\left(n-1\right)$ sequences.
• Starting from a sequence with a zero where the sum of digits is odd, append 1 at the end, adding $\bar{f}\left(n-1\right)$ sequences.
These gives us that $$f\left(n\right)=2f\left(n-1\right)+\bar{f}\left(n-1\right)+g\left(n-1\right)$$
Considering $g\left(n\right)$ first, we are interested in strings of length n from $\left\{ 1,2\right\} $ with an even number of 1s. There's a simple bijection to the set of strings of length $n$ with an odd number of 1s by “flipping” the first value, and as these sets include all possibilities with no overlap, it follows that $g\left(n\right)=2^{n-1}$.
Next looking at $\bar{f}\left(n-1\right)$. We can use the fact that the sequences with a zero where the sum of digits is odd and the sequences with a zero where the sum of digits is even are exactly a disjoint union of all the sequences with a zero.
As there are $n\cdot3^{n-1}$ such sequences (we first choose one location to be 0, and fill the rest normally), we get that $\bar{f}\left(n\right)+f\left(n\right)=n\cdot3^{n-1}$, or $\bar{f}\left(n\right)=n\cdot3^{n-1}-f\left(n\right)$
Putting this all together we get that $$f\left(n\right)=2f\left(n-1\right)+\left(n-1\right)\cdot3^{n-2}-f\left(n-1\right)+2^{n-2}
or f\left(n\right)=f\left(n-1\right)+\left(n-1\right)\cdot3^{n-2}+2^{n-2}$$
Best Answer
Let $E(n)$ count the number of ternary $n$-strings with even sum, and let $e(n)$ count the number of binary $n$-strings, using just the digits $1$ and $2$, with even sum. You want a formula for
$$f(n)=E(n)-e(n)$$
We first note that $e(n)=2^{n-1}$, since the parity of the last digit is determined by the choice of the first $n-1$ digits. As for $E(n)$, if we let $O(n)$ count the number of ternary $n$-strings with odd sum, we see that
$$E(n)=2E(n-1)+O(n-1)=2E(n-1)+(3^{n-1}-E(n-1))=E(n-1)+3^{n-1}$$
Putting these together, we have
$$\begin{align} f(n)&=E(n)-2^{n-1}\\ &=E(n-1)+3^{n-1}-2^{n-1}\\ &=E(n-1)-2^{n-2}+2^{n-2}+3^{n-1}-2^{n-1}\\ &=f(n-1)+3^{n-1}-2^{n-2} \end{align}$$
As a sanity check, we know that $f(1)=1$, so we get
$$\begin{align} f(2)&=1+3-1=3\\ f(3)&=3+9-2=10 \end{align}$$
which can be easily checked by hand. (I find it extremely helpful to run sanity checks, because I almost always make at least one mistake when first deriving a formula. This case was no exception.)
Remark: Once you have the recursive formula $f(n)=f(n-1)+3^{n-1}-2^{n-2}$, it's not hard to prove (by induction) the formula $f(n)=(3^n-2^n+1)/2$ (see Jack D'Aurizio's answer):
$$\begin{align} f(n)&={3^{n-1}-2^{n-1}+1\over2}+3^{n-1}-2^{n-2}\\ &={3^{n-1}-2^{n-1}+1+2\cdot3^{n-1}-2^{n-1}\over2}\\ &={(1+2)3^{n-1}-2\cdot2^{n-1}+1\over2}\\ &={3^n-2^n+1\over2} \end{align}$$