If $t_n$ denotes the number of strings of length $n$ that do not contain $11$ as a substring over the alphabet $\{ 1,2,3 \}$, then prove $t_n = \sum_{i=0}^{\lfloor{\frac{n+1}{2}} \rfloor}2^{n-i} C(n-i+1,i)$.
Here's my attempt:
My attempt was by induction, but I'm stuck at the induction step. We verify the base case and first show $n=1$ holds. $t_1 = 3$, and the desired sum with $n=1$ yields $3$.
For our induction step, suppose $t_n = \sum_{i=0}^{\lfloor{\frac{n+1}{2}} \rfloor} 2^{n-i} C(n-i+1,i)$. Given this, we wish to show $t_{n+1} = \sum_{i=0}^{\lfloor{\frac{n+2}{2}} \rfloor} 2^{n-i+1} C(n-i+2,i)$. Here's where I'm stuck. Is induction even the way to go? If it is, what's the step I should make? If it isn't, where should I look to?
Thanks.
Forget about induction and instead condition on the number $i$ of times that $1$ appears. The remaining $n-i$ digits are $2$ or $3$.