Recurrence relation for a sequence

Question

Find a recurrence for the number of words of length n in the alphabet {1,2,...,k} with no 11. $n\in \mathbb{P}$ with $k \geq2$.

Please help me.....

Answer 1

I'm sure this question has been answered a thousand times before but for a given sequence, consider the case the sequence ends in $1$ or it doesn't:

If it ends in $1$, then the number of possible sequences we can make are $(r-1) W_r(n-2)$. If it doesn't end in $1$, the number of possible sequences we can have are $(r-1)W_r(n-1)$.

This gives us the recurrence relationship:

$$ W_r(n) = (r-1) (W_r(n-1) + W_r(n-2))$$

Solving for $W_r(n)$:

Let $f_r(n)$ be the number of such sequences ending in $1$ and $g_r(n)$ be the number of such sequences not ending in $1$.

Then we have the two relations: $$f_r(n+1) = g_r(n)$$ $$ g_r(n+1) = (r - 1) (f_r(n-1) + g_r(n-1)) $$

If we then

Writing this as a matrix equation:

$$ \left( \begin{array}{c} f_r(n+1) \\ g_r(n+1) \end{array}\right) = \left( \begin{array}{cc} 0 & 1 \\ r-1 & r-1 \end{array}\right) \left( \begin{array}{c} f_r(n) \\ g_r(n) \end{array}\right)$$

We are interested in calculating $$ W_r(n) = \left( \begin{array}{cc} 1 & 1\end{array}\right) A^{n-1} \left( \begin{array}{c} 1 \\ r-1 \end{array}\right) $$

where $A$ is the matrix in the matrix equation. We can then diagonalise $A$ and come up with an exact solution.