Answer :
A recurrence relation for the number of n-digit ternary sequences without consecutive 0s is [tex]a_{n}=\frac{1}{4\sqrt{3}} [(1+\sqrt{3} )^{n+2}-(1-\sqrt{3} )^{n+2}][/tex].
Consider the color of the top chip, if it is red, the he one below cannot be red and the remaining n-2 chips give [tex]a_{n-2}[/tex] different ways.
If it is not red, then the remaining n-1 chips give [tex]a_{n-1}[/tex] different ways.
The recurrence relation is:
[tex]a_{n} = 2a_{n-1}+2a_{n-2}[/tex]
With [tex]a_{1} = 3, a_{2} = 8[/tex]
If you have two poker chips you have 8 ways to make a pile without two consecutive red chips: [tex]wb, bw, rw, wr, rb, br, ww, bb.[/tex] Or you calculate all possible ways and subtract the [tex]rr[/tex] combination: [tex]a_{2} =3^{2}-1=8[/tex]
Similar for [tex]a_{1}[/tex]: The are 3 ways without two consecutive red chips: [tex]r, b, w[/tex]
[tex]a_{1} =3[/tex]
Now, we have to solve the recurrence relation
Using the characteristic equation,
[tex]x^{n}=2x^{n-1}+2^{n-2}[/tex]
Dividing by the smallest power gives,
[tex]x^{2}-2x-2=0[/tex]
Solving for [tex]x[/tex] gives,
[tex]x= 1[/tex]±√3
Then using the general solution:
[tex]a_{n}= A_{1}x_{1}^{n+1}+A_{2}x_{2}^{n+1}[/tex]
Using conditions from above,
[tex]3= A_{1}(1+\sqrt{3} )^{2}+A_{2}(1-\sqrt{3} )^{2}[/tex]
[tex]8= A_{1}(1+\sqrt{3} )^{3}+A_{2}(1-\sqrt{3} )^{3}[/tex]
Therefore the final answer would be
[tex]a_{n} =\frac{3+\sqrt{3} }{12}(1+\sqrt{3} )^{n+1} +\frac{3-\sqrt{3} }{12}(1-\sqrt{3} )^{n+1}[/tex]
[tex]a_{n}=\frac{1}{4\sqrt{3}} [(1+\sqrt{3} )^{n+2}-(1-\sqrt{3} )^{n+2}][/tex]
For more such questions about recurrence relation:
https://brainly.com/question/3694266
#SPJ4