Recurrence relation for a sequence 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.....
 A: 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.
