Find and solve a recurrence relation for the number of ways to make a pile of $n$ poker chips using red, white, and blue chips and such that no two red chips are together (consecutive).
I believe I have found the recurrence relation correctly, however it is solving it where I am running into problems
Part $1)$ Find a recurrence relation
Consider the color of the top chip, if it is red, then he one below cannot be red and the remaining $n-2$ chips give $a_{n-2}$ different ways.
If it is not red, then the remaining $n-1$ chips give $a_{n-1}$ different ways. Then I believe my recurrence relation is
$$a_n = 2a_{n-1}+2a_{n-2}$$
with $a_1=3, a_2=8$
- If you have two poker chips you have 8 ways to make a pile without
two consecutive red chips: $wb,bw,rw,wr,rb,br,ww, bb$. Or you
calculate all possible ways and substract the $rr$ combination: $a_2=3^2-1=8$ - Similar for $a_1$: The are 3 ways without two consecutive red chips:
$r,b,w\Rightarrow a_1=3$
Part $2)$ Solve the recurrence relation
Using the characteristic equation,
$$x^n = 2x^{n-1}+2^{n-2}$$
Dividing by the smallest power gives,
$$x^2-2x-2=0$$
Solving for $x$ gives,
$$x = 1 \pm \sqrt3$$
Then using the general solution:
$$a_n = A_1x_1^{n+1}+A_2x_2^{n+1}$$
Using conditions from above,
$$ 3 = A_1(1+\sqrt3)^2+A_2(1-\sqrt3)^2$$
$$ 8 = A_1(1+\sqrt3)^3+A_2(1-\sqrt3)^3$$
Solving for $A_1, A_2$ I got $A_1 = b=\frac{3+\sqrt{3}}{12}, A_2 = b=\frac{3-\sqrt{3}}{12}$
Therefore the final answer would be
$$a_n = \frac{3+\sqrt{3}}{12}(1+\sqrt3)^{n+1} + \frac{3-\sqrt{3}}{12}(1-\sqrt3)^{n+1}$$
However an answer I found online to this question is the following, so I am not sure where I went wrong in solving it, looking for some help thanks!
$$a_n = \frac{1}{4\sqrt3}\left[ (1+\sqrt3)^{n+2} – (1-\sqrt3)^{n+2}\right]$$
Best Answer
Your solution and the online answer are both correct. Note that your exponents are one higher than the online answer, so split out the extra factor and note that $$\frac {1+\sqrt 3}{4\sqrt 3}=\frac {\sqrt 3+3}{12},\frac {1-\sqrt 3}{4\sqrt 3}=\frac {\sqrt 3-3}{12}$$