Set **a_n** to be this number. We would like to find a
recurrence relation for the sequence of **a_n**'s. Think about
building such a walkway (and have in mind that we have at our
disposal all *good* walkways of shorter length).

If we place a tile in the first position, that of course leaves
us with ** n-1** positions to fill. The next **n-1**
positions constitute a walkway with **n-1** tiles of course.
Clearly this shorter walkway is not permitted to have two
successive Red tiles, so it is one of the **a_(n-1)** many good
walkways of length **n-1**. If the first tile is not Red then
we can put any one of these shorter walkways down and the result
will be a good walkway. Well this accounts for **2*a_(n-1)**
many walkways of length **n** - namely all those that start
with either a Green or Gray tile.

Now let's count the walkways that start with a Red tile. This is
different because we cannot just stick any length **n-1**
walkway after this tile because we may get 2 successive Reds. So
obviously we have to either put a Green or a Gray tile next.
Following that we can certainly put any length **n-2** tile AND
conversely every walkway that starts out RED GREEN is followed by
a length **n-2** good walkway. Similarly for RED GRAY starting
walkways. Therefore there are **a_(n-2) ** good walkways that
start RED GREEN and an equal number that start RED GRAY.

Finally our desired recurrence relation is: **a_n = 2*a_(n-1) +
2*a_(n-2)**

The initial conditions are ** a_0 = 1** and **a_1=3** since
there is exactly 1 walkway with no tiles and exactly 3 with 1
tile.

What is **a_7**? Well just start churning out the terms:

**a_2 = 2*a_1 + 2*a_0 = 2*3+2*1 = 8 **

a_4=2*22+2*8=44+16=60

a_5 = 2*60+2*22=120+44=164

a_6=2*164+2*60=328+120=448

a_7=2*448+2*164= 896+328= 1224

Well what are we learning next? This recurrence relation, ** a_n
= 2*a_(n-1)+2*a_(n-2)**, has characteristic equation:
** r^2 - 2*r - 2= 0**. This characteristic equation has two
distinct roots or solutions. Just use the quadratic formula: the
solutions to ** ax^2 + bx + c = 0** are given by the formula:
** (-b +/- SQRT(b^2 - 4ac) )/2a**. In our case **a=1**,
while **b=c=2**. So the solutions are **-(-2) +
SQRT((-2)^2-4*(-2) )/2** and **-(-2) - SQRT( (-2)^2-4*(-2)
)/2**. These simplify to

**
r_1 = 1 + SQRT(3)**

and

Very important, any solution to the characteristic equation yields
a solution to the recurrence relation by just taking its
powers.**
I.e. { (1+SQRT(3))^n } for n = 0,1,2,... is a solution**

AND

Why is that true? Simply if **r** is a solution to ** r^2 - 2r
- 2 =0**, then clearly **r** has the property that

** r^2 = 2*r + 2 **

hence

since all we did was to multiply both sides by

Also, as we discovered, if we add two solutions together we get
more solutions. In fact if we pick any two real numbers, call them
**A ** and **B**, (or even complex numbers), then

** { A*r_1^n + B * r_2^n } ** is yet another solution. We
finish * solving* this recurrence relation by finding
suitable values for **A** and **B** so that we also get the
right initial conditions.

That is we want: ** a_0 = 1** and ** a_1 = 3**. Set up the
required two equations:

** a_0 = 1 = A * (r_1)^0 + B * (r_2)^0 = A + B**

and

** a_1 = 3 = A * (r_1)^1 + B * (r_2)^1 = A*r_1 + B*r_2 **

Remember that **r_1 ** and **r_2** are known values (above)
and we want to solve for **A** and **B**. Take the second
equation and subtract
**r_2**
times the first equation
(this will eliminate the **B** term):

**
3 - r_2*1 = ( A*r_1 - r_2*A ) + ( B * r_2 - r_2 * B ) =
A * (r_1 - r_2)**

hence

** A = (3 - r_2 ) / (r_1 - r_2) ** (we are using that **r_1
**
is not equal to **r_2**). Plug this value for **A** into one
of the equations (easiest to use the first) and solve for
**B**.

** 1 = A + B** hence ** B = 1 - (3 - r_2) /
(r_1 - r_2) = ( (r_1 - r_2 ) - (3 - r_2 ) ) / (r_1 - r_2) =
( r_1 - 3) / (r_1 - r_2)**. Well finally plug in for **r_1 =
1 + SQRT(3)** and **r_2 = 1 - SQRT(3)**. This give us the
real
numerical values for **A** and **B** which we plug back into
the equation: ** a_n = A * (r_1)^n + B * (r_2)^n **. Since **
r_1 - r_2 = 2*SQRT(3)**:

** A = (3 - r_2 ) / (r_1 - r_2) = ( 3 - (1-SQRT(3) )/
(2*SQRT(3)) = ( 2 + SQRT(3) ) / (2*SQRT(3))
**

and

Hence

`
`

(2 + SQRT(3)) * (1+SQRT(3))^n + (SQRT(3) -2) * (1-SQRT(3))^n a_n = ------------- ------------ (2*SQRT(3)) (2*SQRT(3))

Let's try **a_7**: **(1+SQRT(3))^7 = 1136.1127** and
**(1-SQRT(3))^7 = -0.1127**. Also
**A = 1.0774 ** and **B = -0.0774**, so finally:

** A (r_1)^7 + B (r_2)^7 = (1.0774)*(1136.1127) + (-0.0774)*(-0.1127)
= 1224.0565 **

* I guess my calculator has round off errors*.