All the ternary n-words with an even sum of digits and a zero.

Question

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}$$

Answer 1

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}$$

Answer 2

Your error is the count of $\overline f(n-1)$. In the next paragraph, you are counting $\overline f(n)$, not $\overline f(n-1)$. You also count strings with more than one zero multiple times. The string $0001$ would be counted three times, once for each zero. I don't see how you get non-integral values--there is no division anywhere.

Added: I would also define $\overline g(n)$ as the strings of odd sum and no zeros. Your argument that $g(n)=2^{n-1}$ applies to $\overline g(n)$ as well. Your recurrence for $f(n)$ is fine. To get $\overline f(n)$ you can start with $\overline f(n-1)$ and append a $0$ or $2$,start with a string of length $n-1$ and even sum and append a $1$, or start with a string of length $n-1$ with odd sum and no zeros and append a zero. Your argument for $g(n)$ applies to the last, so $\overline f(n)=2\overline f(n-1)+f(n-1)++\overline g(n-1)=2\overline f(n-1)+f(n-1)$+2^{n-2}$

Answer 3

The recurrence approach is not strictly needed. The parity of the digit sum obviously depends on the number of $1$s only; the number of ternary strings having length $n$ with exactly $k$ digits $1$ and at least one digit $0$ is $\binom{n}{k}\cdot\left(2^{n-k}-1\right)$. The answer is so:

$$\begin{eqnarray*} \sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2j}\left(2^{n-2j}-1\right)&=&-2^{n-1}+\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2j}2^{n-2j}\\&=&-2^{n-1}+\frac{1}{2}\sum_{k=0}^{n}\binom{n}{k}2^{n-k}((-1)^k+1^k)\\&=&\color{red}{\frac{3^n-2^n+1}{2}}.\end{eqnarray*} $$ That makes sense: we have $2^n$ strings without digits $0$, and among the remaining $3^n-2^n$ it is reasonable to expect that about half of them has an even digit sum.

Answer 4

Inspired by Jack D'Aurizio's post:

There are $\ 3^n$ ternary strings of length $\ n$ altogether, and $\ 2^n$ have no $\ 0$. Of the remaining $\ 3^n - 2^n$, one is the string with nothing but $\ 0$, and the rest have at least one non-zero element. As you noted in your own proof, the map that swaps the first non-zero element between $\ 1$ and $\ 2$ is a bijection between those strings with even and odd sums. So $$\frac{3^n - 2^n - 1}{2}$$ of them will be even. Adding in the $\ 0$-string as also having an even sum gives $$\frac{3^n - 2^n + 1}{2}$$ as the number of strings with at least one $\ 0$ and even sum.

Answer 5

As an addendum to Barry's answer above, here I show how to solve for the closed form of the recurrence relation directly.

Given the recurrence of the form $f(n)=f(n-1)+3^{n-1}-2^{n-2}$ and the initial condition $f(1)=1$ we first find what the homogeneous solution will look like.

The characteristic polynomial will be of the form $x-1=0$, so we know the final solution will be of the form: $f(n)=c_1\cdot (1)^n + p(n)$ for some particular solution $p(n)$.

Given our non-homogenous part, we expect $p(n)=d_13^n+d_22^n$ for some constants $d_1$ and $d_2$. Plugging this in for $f(n)$ and $f(n-1)$ respectively we have:

$d_13^n+d_22^n=d_13^{n-1}+d_22^{n-1}+3^{n-1}-2^{n-2}$

By grouping similarly ordered terms, this implies the following system of equations:

$\begin{cases}3d_1=d_1+1\\4d_2=2d_2-1\end{cases}$

which implies $d_1=\frac{1}{2}$ and $d_2=-\frac{1}{2}$

So, we have $f(n)=c_1+\frac{1}{2}3^n-\frac{1}{2}2^n$

Using our initial condition, we solve for $c_1$

$1=c_1+\frac{1}{2}3^1-\frac{1}{2}2^1=c_1+\frac{1}{2}$ implying $c_1=\frac{1}{2}$

Thus, $f(n)=\frac{1}{2}+\frac{1}{2}3^n-\frac{1}{2}2^n=\frac{3^n-2^n+1}{2}$