My Attempts
First I wrote down some numbers
Of length one, there is only $1$ valid number – $2$
Of Length two there are $4$: $12, 20, 21, 22$
Of Length three there are $13$: $112, 120, … , 221, 222$
….
Of that I got a sequence ${1, 4, 13, 40, 121, 364, …}$
I then found the relation
$$a_n = \left\{ \begin{array}{cl}
a_1 & = \ 1 \\
a_n & = \ a_{n-1} * 3 + 1
\end{array} \right.$$
Which is
$$ \frac{3^n – 1}{2}$$
Knowing that I wanted to prove this sequence holds for any string of length n.
I tried to prove this via combinations
-Of length one there are ${1}\choose{1}$ = 1 results
-Of length two there are ${2}\choose{1}$ + ${2}\choose{2}$ = 3 ?
That didn't work, so then I tried
-The total strings of length 1 minus the total with NO twos is $3^1$ – $2^1$ = $1$
-Of Length 2 is $3^2$ – $2^2$ = $5$ ?
This also doesn't work, so then I tried looking at the strings themselves again
The strings of length $2$ contains… $3$ strings with one $2$, $1$ with $2$ twos
The strings of length $3$ contains $7$ with $1$, $5$ with $2$, and $1$ with $3$
Of length $3$: $15$ with $1$, $17$ with $2$, $7$ with $3$, $1$ with $4$
Now I have all these numbers, but I am at a loss what to do with them.
Where did I go wrong about attempting to do this? (Probably something very blatant)
And how do I finish it?
Best Answer
As explained in the comments, for problems like this where you have to count multiple cases (at least one $2$ includes exactly one $2$, exactly two $2$'s, ...), it's often easier to count the complement first to avoid the overlap double-counting challenge. So in this case,
Number of strings that contain at least one $2$ = Total number of strings - Number of strings that contain zero $2$'s
To qualify as a $n$-digit ternary string, first digit cannot be $0$. So there are only two possibilities: $1$ or $2$. The remaining $n-1$ digits can be either $0,1,2$ independently. So the total number of $n$-digit ternary strings is $2\times3^{n-1}$.
When there are zero $2$'s, that's basically counting the total number when only $0$ and $1$ are valid digits. Since $0$ cannot be the first digit, similar to above, we get $1\times2^{n-1}$.
So the number of $n$-digit ternary strings with at least one $2$, is $2\times3^{n-1} - 2^{n-1}$