<s>[INST] Find and solve a recurrence relation In a casino, there are $k(\geq 2)$ colored poker chips, one of which is blue. Find and solve a recurrence relation for the number of ways Joseph can stack n of these chips without consecutive blue chips.
Attempt
Let $a_n$ be the number of such arrangements of $n$ poker chips. If we look at the chip, the one underneath it must be of $k-1$ different colours, so we have $(k-1)a_{n-2}$ ways to arrange the rest of the stack. If it's one the other $k-1$ chips on top, we have $a_{n-1}$ ways to arrange the rest of the stack.
Therefore, we're trying to solve the following recurrence relation:
\begin{align*}
a_n=(k-1)a_{n-1}+(k-1)a_{n-2}, n\geq 2
\end{align*}
With $a_0=1$ y $a_1=k$.
Is this correct?
 [/INST] If the reccurence relation is
$$a_n=(k-1)(a_{n-1}+a_{n-2})$$ the solution is given by
$$a_n=\frac {2^{-(n+1)}} K \Big[(K-k-1) (k-K-1)^n+(K+k+1) (k+K-1)^n\big]$$ where $K=\sqrt{(k-1)(k+3)}$.
This generates the sequence
$$\left(
\begin{array}{cc}
 0 & 1 \\
 1 & k \\
 2 & (k-1) (k+1) \\
 3 & (k-1) \left(k^2+k-1\right) \\
 4 & (k-1)^2 k (k+2) \\
 5 & (k-1)^2 \left(k^3+2 k^2-k-1\right) \\
 6 & (k-1)^3 (k+1) \left(k^2+2 k-1\right) \\
 7 & (k-1)^3 k \left(k^3+3 k^2-3\right) \\
 8 & (k-1)^4 \left(k^2+k-1\right) \left(k^2+3 k+1\right) \\
 9 & (k-1)^4 \left(k^5+4 k^4+2 k^3-5 k^2-2 k+1\right) \\
 10 & (k-1)^5 k (k+1) (k+2) \left(k^2+2 k-2\right)
\end{array}
\right)$$ where interesting patterns can be found.
</s>